字典树

问题

字典树（Trie）的原理和常见题目有哪些？

答案

Trie 树（前缀树）用于高效存储和查找字符串集合，特别适合前缀匹配。

Trie 实现（LeetCode 208）

标准 Trie 实现

class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd = false;
    
    // 插入单词
    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    
    // 查找完整单词
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    // 查找前缀
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    
    private Trie searchPrefix(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

单词搜索 II（LeetCode 212）

Trie + DFS 回溯

public List<String> findWords(char[][] board, String[] words) {
    Trie root = new Trie();
    for (String word : words) root.insert(word);
    
    Set<String> result = new HashSet<>();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs(board, i, j, root, new StringBuilder(), result);
        }
    }
    return new ArrayList<>(result);
}

private void dfs(char[][] board, int i, int j, Trie node, 
                 StringBuilder path, Set<String> result) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length 
        || board[i][j] == '#') return;
    
    char c = board[i][j];
    if (node.children[c - 'a'] == null) return;
    
    node = node.children[c - 'a'];
    path.append(c);
    if (node.isEnd) result.add(path.toString());
    
    board[i][j] = '#';  // 标记已访问
    dfs(board, i+1, j, node, path, result);
    dfs(board, i-1, j, node, path, result);
    dfs(board, i, j+1, node, path, result);
    dfs(board, i, j-1, node, path, result);
    board[i][j] = c;    // 回溯
    path.deleteCharAt(path.length() - 1);
}

搜索推荐系统（LeetCode 1268）

Trie 存储 + DFS 收集前缀匹配结果

// 在每个 Trie 节点维护经过该节点的最优（字典序最小）3 个单词
// 用户每输入一个字符，沿 Trie 走一步，返回对应节点的推荐列表

---

常见面试问题

Q1: Trie 的时间和空间复杂度？

答案：

• 插入/查找：$O(L)$，L 为字符串长度
• 空间：最坏 $O(N \times L \times 26)$，N 个长度为 L 的字符串
• 优点：前缀查询 $O(L)$，比 HashSet 的 $O(L)$ 更适合前缀场景

Q2: Trie vs HashMap 存储字符串集合？

答案：

对比	Trie	HashMap
精确查找	$O(L)$	$O(L)$（计算哈希也是 $O(L)$）
前缀查询	$O(L)$，天然支持	不支持，需遍历所有 key
空间	较大（每个节点 26 个指针）	较小
适用场景	自动补全、拼写检查	精确匹配

Q3: 如何优化 Trie 的空间？

答案：

• 用 HashMap<Character, Trie> 替代 Trie[26] 数组（稀疏时节省空间）
• 压缩 Trie（Radix Tree）：合并只有一个子节点的连续节点

相关链接

• 回溯与搜索
• 字符串