算法刷题系列（二十一）：字典树——按公共前缀组织字符串

算法刷题系列（二十一）：字典树——按公共前缀组织字符串

KMP 利用一个模式串内部的前后缀关系加速匹配。本篇从多个字符串共享前缀的角度组织数据：字典树（Trie）把字符逐层放入节点路径，让具有相同前缀的单词共享节点。

它适合前缀查询、自动补全和词典查找。若只做少量完整单词查询，哈希集合通常更简单；当业务频繁查询“是否存在以某前缀开头的单词”时，字典树才体现出优势。

一、从单词集合到前缀路径

插入以下单词：

cat
car
care
dog

cat 和 car 共享路径 c -> a；car 和 care 继续共享 r。节点需要区分两种状态：

• 是否存在从根到当前节点的完整单词；
• 是否还有子节点延伸出更长单词。

所以 car 对应的节点即使有子节点 e，也必须标记为一个完整单词。

二、操作与复杂度

设单词长度为 L：

• 插入：O(L)；
• 查询完整单词：O(L)；
• 查询前缀：O(L)。

复杂度主要按字符数计算，与字典中的单词数量关系较小。空间取决于所有单词的节点总数和字符集表示方式。

三、Java 实现：小写英文字母 Trie

此版本约定输入只能包含 a 到 z，使用长度为 26 的数组保存子节点。遇到非法字符会显式报错，而不是悄悄跳过。

public class Trie {
    private static final class Node {
        private final Node[] children = new Node[26];
        private boolean isWord;
    }

    private final Node root = new Node();

    public void insert(String word) {
        validate(word);
        Node current = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (current.children[index] == null) {
                current.children[index] = new Node();
            }
            current = current.children[index];
        }
        current.isWord = true;
    }

    public boolean search(String word) {
        validate(word);
        Node node = findNode(word);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        validate(prefix);
        return findNode(prefix) != null;
    }

    private Node findNode(String text) {
        Node current = root;
        for (int i = 0; i < text.length(); i++) {
            int index = text.charAt(i) - 'a';
            current = current.children[index];
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    private static void validate(String text) {
        if (text == null) {
            throw new IllegalArgumentException("text must not be null");
        }
        for (int i = 0; i < text.length(); i++) {
            char current = text.charAt(i);
            if (current < 'a' || current > 'z') {
                throw new IllegalArgumentException(
                    "text may contain only lowercase English letters"
                );
            }
        }
    }
}

空字符串可以被插入并标记为根节点上的单词；空前缀也匹配根节点。若题目不允许空串，可以在输入校验中增加相应限制。

四、Python 实现：字典子节点

Python 版本使用字典保存实际出现的字符，不限定为小写英文字母，因此可以处理任意 Python 字符序列。每个节点仍显式保存终止标记。

from __future__ import annotations

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_word = False

class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        if word is None:
            raise ValueError("word must not be None")
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_word = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_word

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, text: str) -> TrieNode | None:
        if text is None:
            raise ValueError("text must not be None")
        current = self.root
        for char in text:
            current = current.children.get(char)
            if current is None:
                return None
        return current

trie = Trie()
for word in ("cat", "car", "care", "dog"):
    trie.insert(word)
trie.insert("")
assert trie.search("car")
assert not trie.search("ca")
assert trie.starts_with("ca")
assert not trie.starts_with("cab")
assert trie.search("")

如果运行环境低于 Python 3.10，可在代码开头加 from __future__ import annotations，以兼容 TrieNode | None 这类注解写法。

五、边界与实现取舍

1. 完整单词与前缀不是同一件事：路径存在只能说明是前缀，必须检查 isWord 才能判定完整单词。
2. 固定数组还是映射：字符集很小且固定时数组访问快；字符集稀疏或范围大时，映射更节省空间。
3. 重复插入：把终止标记设为 true 即可，默认集合语义不会增加重复单词。
4. 删除操作：本文未实现删除。实际删除要区分清除单词标记与剪掉不再被其他词使用的节点。
5. 大小写和规范化：字典树本身不自动把大小写、重音或 Unicode 等价字符视为相同；应用需要先规定规范化策略。

六、字典树与哈希表怎么选？

哈希集合查询完整单词通常实现更简单，平均 O(L) 的字符串散列/比较成本因语言实现而异；字典树可共享前缀，并支持逐字符前缀查询。字典树不一定总更省空间：固定子节点数组会为稀疏节点预留空位。

若只是判断一批词是否存在，优先考虑哈希集合；若需要大量前缀查询、按前缀枚举或逐字符搜索，字典树更自然。

小结

字典树把字符串集合组织成共享前缀的路径。查完整单词要检查终止标记，查前缀只需确认路径存在。实现前先明确字符集、空串和大小写规范，再选择数组或映射作为子节点容器。