208 实现 Trie（前缀树）

一、题目

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

请你实现 Trie 类：

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

二、题解

思路：前缀树 Trie。

1. 核心思路

前缀树是一种专门用来存储字符串的树形结构。

因为题目中的字符串只包含小写英文字母，所以每个节点最多有 26 个子节点，分别表示字母 a 到 z。

每个 Trie 节点需要保存两个信息：

TrieNode[] children = new TrieNode[26];
boolean isEnd;

其中：

  • children[i] 表示当前节点是否存在对应字母的子节点。
  • isEnd 表示当前节点是否是某个完整单词的结尾。

例如插入单词 apple 后，前缀树可以表示为：

root
  |
  a
  |
  p
  |
  p
  |
  l
  |
  e  ← isEnd = true

虽然 app 是 apple 的前缀，但此时 app 还没有作为完整单词插入，所以：

search("app");       // false
startsWith("app");   // true

2. 具体步骤

  1. 定义 Trie 节点，每个节点包含一个长度为 26 的子节点数组和一个单词结束标记。
  2. 创建一个不表示任何字符的根节点 root。
  3. 插入单词时，从根节点开始，依次处理每个字符。
  4. 如果当前字符对应的子节点不存在，就创建一个新节点。
  5. 单词遍历结束后，将最后一个节点的 isEnd 标记为 true。
  6. 搜索单词时，先判断字符串对应的路径是否存在，再判断最后一个节点的 isEnd 是否为 true。
  7. 搜索前缀时，只需要判断字符串对应的路径是否存在，不需要判断 isEnd。

3. 关键逻辑

字符转换为数组下标

由于字符串只包含小写英文字母，可以使用：

int index = c - 'a';

将字符转换为 0～25 的数组下标：

'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2
...
'z' - 'a' = 25

插入单词

遍历单词中的每个字符：

  • 如果对应的子节点不存在，就创建新节点。
  • 移动到对应的子节点。
  • 遍历结束后，将最后一个节点标记为单词结尾。
node.isEnd = true;

搜索完整单词

搜索完整单词需要满足两个条件：

  1. 单词中每个字符对应的路径都存在。
  2. 最后一个节点的 isEnd 为 true。
return node != null && node.isEnd;

例如只插入 apple：

search("apple"); // true
search("app");   // false

app 的路径虽然存在，但最后一个 p 节点的 isEnd 为 false，所以它不是一个完整单词。

搜索前缀

搜索前缀只要求所有字符对应的路径存在，不要求最后一个节点是单词结尾。

return findNode(prefix) != null;

例如只插入 apple：

startsWith("app"); // true

因为前缀树中存在 a → p → p 这条路径。

三、代码

class Trie {

    /**
     * 前缀树节点
     */
    private static class TrieNode {

        // children[0] 表示字符 a
        // children[1] 表示字符 b
        // ...
        // children[25] 表示字符 z
        TrieNode[] children = new TrieNode[26];

        // 当前节点是否为某个完整单词的结尾
        boolean isEnd;
    }

    // 前缀树的根节点
    private final TrieNode root;

    /**
     * 初始化前缀树
     */
    public Trie() {
        root = new TrieNode();
    }

    /**
     * 向前缀树中插入字符串 word
     */
    public void insert(String word) {
        TrieNode node = root;

        for (char c : word.toCharArray()) {
            // 将字符转换为 0～25 的数组下标
            int index = c - 'a';

            // 当前字符对应的节点不存在，创建新节点
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }

            // 移动到下一个节点
            node = node.children[index];
        }

        // 将最后一个节点标记为完整单词的结尾
        node.isEnd = true;
    }

    /**
     * 判断完整字符串 word 是否存在
     */
    public boolean search(String word) {
        TrieNode node = findNode(word);

        // 路径存在，并且最后一个节点是单词结尾
        return node != null && node.isEnd;
    }

    /**
     * 判断是否存在以 prefix 开头的字符串
     */
    public boolean startsWith(String prefix) {
        // 搜索前缀只需要判断路径是否存在
        return findNode(prefix) != null;
    }

    /**
     * 查找字符串对应的最后一个节点
     *
     * 如果中途路径不存在，返回 null；
     * 如果路径存在，返回最后一个字符对应的节点。
     */
    private TrieNode findNode(String str) {
        TrieNode node = root;

        for (char c : str.toCharArray()) {
            int index = c - 'a';

            // 当前字符对应的路径不存在
            if (node.children[index] == null) {
                return null;
            }

            // 移动到下一个节点
            node = node.children[index];
        }

        return node;
    }
}

四、复杂度分析

设本次操作的字符串长度为 LL，前缀树中存储的所有字符串的字符总数为 SS。

时间复杂度：O(L)O(L)

说明：无论是插入单词、搜索单词还是搜索前缀，都需要依次遍历字符串中的每个字符。

空间复杂度：O(S)O(S)

说明：最坏情况下，每个字符都需要创建一个新的 Trie 节点。虽然每个节点内部有一个长度为 26 的数组，但 26 是常数，因此整体空间复杂度为 O(S)O(S)。

评论