Trie Applications: Word Search and Substitution

Replace Words (LeetCode 648)

Given a dictionary of roots, replace every derived word in a sentence with the shortest root that forms the prefix of that word.

public String replaceWords(List<String> dictionary, String sentence) {
    TrieNode root = new TrieNode();
    // Build the Trie
    for (String rootWord : dictionary) {
        TrieNode cur = root;
        for (char c : rootWord.toCharArray()) {
            if (cur.children[c - 'a'] == null) cur.children[c - 'a'] = new TrieNode();
            cur = cur.children[c - 'a'];
        }
        cur.word = rootWord; // Store root in the leaf
    }
    
    String[] words = sentence.split(" ");
    StringBuilder sb = new StringBuilder();
    for (String w : words) {
        if (sb.length() > 0) sb.append(' ');
        TrieNode cur = root;
        for (char c : w.toCharArray()) {
            // Stop if we hit a leaf (shortest root found) or a dead end
            if (cur.children[c - 'a'] == null || cur.word != null) break;
            cur = cur.children[c - 'a'];
        }
        sb.append(cur.word != null ? cur.word : w);
    }
    return sb.toString();
}

static class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word;
}

Design Search Autocomplete System (LeetCode 642)

A system that tracks historical search frequency and provides the top 3 suggestions as the user types.

class AutocompleteSystem {
    private TrieNode root = new TrieNode();
    private TrieNode current;
    private StringBuilder input = new StringBuilder();

    public AutocompleteSystem(String[] sentences, int[] times) {
        current = root;
        for (int i = 0; i < sentences.length; i++) insert(sentences[i], times[i]);
    }

    private void insert(String s, int t) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            if (!node.children.containsKey(c)) node.children.put(c, new TrieNode());
            node = node.children.get(c);
        }
        node.count += t;
    }

    public List<String> input(char c) {
        if (c == '#') {
            insert(input.toString(), 1);
            current = root;
            input.setLength(0);
            return Collections.emptyList();
        }
        input.append(c);
        if (current != null) current = current.children.get(c);
        
        // DFS to collect all candidates starting with current prefix
        List<Candidate> candidates = new ArrayList<>();
        dfs(current, input.toString(), candidates);
        
        // Sort by frequency (desc) and lexicographical order (asc)
        candidates.sort((a, b) -> a.count != b.count ? b.count - a.count : a.sentence.compareTo(b.sentence));
        
        List<String> result = new ArrayList<>();
        for (int i = 0; i < Math.min(3, candidates.size()); i++) result.add(candidates.get(i).sentence);
        return result;
    }

    private void dfs(TrieNode node, String prefix, List<Candidate> res) {
        if (node == null) return;
        if (node.count > 0) res.add(new Candidate(prefix, node.count));
        for (char c : node.children.keySet()) {
            dfs(node.children.get(c), prefix + c, res);
        }
    }

    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        int count;
    }
    
    static class Candidate {
        String sentence;
        int count;
        Candidate(String s, int c) { this.sentence = s; this.count = c; }
    }
}

Search Suggestions System (LeetCode 1268)

Return up to three suggestions after each character of a search word is typed.

public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products); // Lexicographical order is key
    List<List<String>> result = new ArrayList<>();
    int lo = 0, hi = products.length - 1;
    
    for (int i = 0; i < searchWord.length(); i++) {
        char c = searchWord.charAt(i);
        // Narrow the range based on current prefix character
        while (lo <= hi && (products[lo].length() <= i || products[lo].charAt(i) != c)) lo++;
        while (lo <= hi && (products[hi].length() <= i || products[hi].charAt(i) != c)) hi--;
        
        List<String> currentList = new ArrayList<>();
        for (int j = lo; j <= Math.min(lo + 2, hi); j++) {
            currentList.add(products[j]);
        }
        result.add(currentList);
    }
    return result;
}

Note: While this can be solved with a Trie, sorted two-pointer contraction is often more memory-efficient and simpler to implement.

Short Encoding of Words (LeetCode 820)

Calculate the minimum length of a reference string where every word in the dictionary is a suffix of some portion of the reference string.

public int minimumLengthEncoding(String[] words) {
    Set<String> set = new HashSet<>(Arrays.asList(words));
    // Any word that is a suffix of another word can be skipped
    for (String w : words) {
        for (int i = 1; i < w.length(); i++) {
            set.remove(w.substring(i));
        }
    }
    int total = 0;
    for (String w : set) {
        total += w.length() + 1; // Content length + '#' delimiter
    }
    return total;
}

Reverse Trie Insight: This problem can be solved by inserting all reversed words into a Trie. Each path from a root to a leaf node represents a unique suffix encoding. 筋