Trie 应用：单词搜索与替换

单词替换（LeetCode 648）

给定词根列表，在句子中将衍生词替换为最短词根。

public String replaceWords(List<String> dictionary, String sentence) {
    TrieNode root = new TrieNode();
    // 建 Trie
    for (String root_word : dictionary) {
        TrieNode cur = root;
        for (char c : root_word.toCharArray()) {
            if (cur.children[c-'a'] == null) cur.children[c-'a'] = new TrieNode();
            cur = cur.children[c-'a'];
        }
        cur.word = root_word;   // 叶节点存词根
    }
    
    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()) {
            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;
}

自动补全系统（LeetCode 642）

热门句子系统：输入每个字符后，返回历史热门3条。

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

    public AutocompleteSystem(String[] sentences, int[] times) {
        cur = 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[c] == null) node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.count += t;
    }

    public List<String> input(char c) {
        if (c == '#') {
            insert(input.toString(), 1);
            cur = root;
            input.setLength(0);
            return List.of();
        }
        input.append(c);
        if (cur != null) cur = cur.children[c];
        // DFS 收集候选，按频率降序、字典序升序
        List<String[]> candidates = new ArrayList<>();
        dfs(cur, input.toString(), candidates);
        candidates.sort((a, b) -> {
            int diff = Integer.parseInt(b[1]) - Integer.parseInt(a[1]);
            return diff != 0 ? diff : a[0].compareTo(b[0]);
        });
        List<String> res = new ArrayList<>();
        for (int i = 0; i < Math.min(3, candidates.size()); i++) res.add(candidates.get(i)[0]);
        return res;
    }

    private void dfs(TrieNode node, String prefix, List<String[]> res) {
        if (node == null) return;
        if (node.count > 0) res.add(new String[]{prefix, String.valueOf(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;
    }
}

搜索推荐系统（LeetCode 1268）

输入每个前缀后，返回字典序最小的3个匹配产品。

public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products);
    List<List<String>> res = new ArrayList<>();
    int lo = 0, hi = products.length - 1;
    for (int i = 0; i < searchWord.length(); i++) {
        char c = searchWord.charAt(i);
        // 缩小范围：lo/hi 找到以当前前缀开头的范围
        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> cur = new ArrayList<>();
        for (int j = lo; j <= Math.min(lo + 2, hi); j++) cur.add(products[j]);
        res.add(cur);
    }
    return res;
}

此解法无需建 Trie，利用排序后二分思想，更简洁。

短路径词语（LeetCode 820）

求单词列表的最小前缀编码长度。

public int minimumLengthEncoding(String[] words) {
    Set<String> set = new HashSet<>(Arrays.asList(words));
    // 如果一个单词是另一个的后缀，它不需要单独编码
    for (String w : words)
        for (int i = 1; i < w.length(); i++)
            set.remove(w.substring(i));
    int res = 0;
    for (String w : set) res += w.length() + 1;  // +1 for '#'
    return res;
}

反向 Trie：将所有单词反转后建 Trie，每条从根到叶路径是一个独立后缀。