跳到主要内容

字典树 (Trie)

字典树又称前缀树，核心结构是 TrieNode，每个节点包含一个 TrieNode[26] 数组和一个布尔值 isEnd。

208. 实现 Trie (Prefix Tree)​

题目描述​

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

解题思路​

嵌套节点遍历。

  1. insert：从根开始，根据字符找到对应 index，如果为空则新建节点，最后标记 isEnd = true。
  2. search：顺着链路找，如果能找完整个字符串且最后的节点 isEnd 为 true。
  3. startsWith：同 search，但最后不需要校验 isEnd，只要节点不空。

Java 代码实现​

class Trie {
    class Node { Node[] next = new Node[26]; boolean isEnd; }
    Node root = new Node();
    public void insert(String word) {
        Node curr = root;
        for (char c : word.toCharArray()) {
            if (curr.next[c - 'a'] == null) curr.next[c - 'a'] = new Node();
            curr = curr.next[c - 'a'];
        }
        curr.isEnd = true;
    }
    public boolean search(String word) {
        Node node = find(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }
    private Node find(String s) {
        Node curr = root;
        for (char c : s.toCharArray()) {
            if (curr.next[c - 'a'] == null) return null;
            curr = curr.next[c - 'a'];
        }
        return curr;
    }
}

211. 添加与搜索单词 - 数据结构设计 (Design Add and Search Words Data Structure)​

题目描述​

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

  • WordDictionary() 初始化词典对象
  • void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
  • bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。 word 中可能包含一些 '.' ，每个 '.' 都可以表示任何一个字母。

解题思路​

Trie + 回溯搜索。

  1. 插入逻辑同标准 Trie。
  2. 查找逻辑：当遇到 . 时，需要遍历当前节点的所有 next[i] 非空节点。

Java 代码实现​

class WordDictionary {
    private class Node { Node[] next = new Node[26]; boolean end; }
    private Node root = new Node();
    public void addWord(String word) {
        Node curr = root;
        for (char c : word.toCharArray()) {
            if (curr.next[c - 'a'] == null) curr.next[c - 'a'] = new Node();
            curr = curr.next[c - 'a'];
        }
        curr.end = true;
    }
    public boolean search(String word) {
        return dfs(word, 0, root);
    }
    private boolean dfs(String s, int idx, Node node) {
        if (idx == s.length()) return node.end;
        char c = s.charAt(idx);
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (node.next[i] != null && dfs(s, idx + 1, node.next[i])) return true;
            }
            return false;
        } else {
            return node.next[c - 'a'] != null && dfs(s, idx + 1, node.next[c - 'a']);
        }
    }
}

212. 单词搜索 II (Word Search II)​

题目描述​

给定一个 m x n 个单元格的网格 board 和一个名单 words，找出所有同时在网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

解题思路​

Trie + 回溯 + 状态标记。

  1. 将所有 words 插入前缀树中。
  2. 遍历网格中的每一个单元格，作为起点开始 DFS。
  3. 在 DFS 过程中，通过前缀树来判断当前路径构成的字符串是否为某个单词的前缀。
  4. 如果不是，则剪枝；如果是，且当前节点标记了 word 结尾，则收集单词。
  5. 技巧：在 DFS 过程中将 board[i][j] 暂时修改为特殊字符（如 '#'）来标记已访问，回溯时复原。

Java 代码实现​

class Solution {
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode curr = root;
            for (char c : w.toCharArray()) {
                if (curr.next[c - 'a'] == null) curr.next[c - 'a'] = new TrieNode();
                curr = curr.next[c - 'a'];
            }
            curr.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }
    private void dfs(char[][] b, int r, int c, TrieNode node, List<String> res) {
        char ch = b[r][c];
        if (ch == '#' || node.next[ch - 'a'] == null) return;
        node = node.next[ch - 'a'];
        if (node.word != null) {
            res.add(node.word);
            node.word = null; // 防止重复
        }
        b[r][c] = '#';
        int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr >= 0 && nr < b.length && nc >= 0 && nc < b[0].length) {
                dfs(b, nr, nc, node, res);
            }
        }
        b[r][c] = ch;
    }
}