Implement Trie (Prefix Tree)

Q: 字典树的时间复杂度是多少？

插入、搜索和 startsWith 每个操作都要沿着每个字母对应的一条链接前进，因此对于长度为 L 的单词，每个操作都需要 O(L) ，与存储的单词数量无关。空间复杂度为 O(T) ，其中有 T 个已插入的字母节点，每个节点最多有 26 条子链接。

Q: 为什么使用字典树而不是哈希集合？

哈希集合可以在 O(L) 时间内查找完整单词，但如果不扫描每个单词，就无法回答前缀查询。将每个前缀存入另一个集合，仅存储一个 20 个字母的单词就需要 210 个字母。Trie 会将每个共享前缀只存储一次，并通过一次遍历回答这两个问题。

中等字典树

+10

为小写单词构建一个字典树（前缀树），支持三种操作：insert w 添加单词 w，search w 用于判断是否插入了单词 w 本身，startsWith p 用于判断是否有某个已插入的单词以 p 开头。单词本身也算作它自己的前缀。

操作 i 是对 words[i] 执行的 ops[i]。按顺序在一个空字典树上执行这些操作，并为每个操作返回一个字符串：插入操作返回 "null"，搜索操作或 startsWith 操作返回 "true" 或 "false"。

函数

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: 这些操作及其运行顺序
wordsstring-array: 每个操作对应的单词或前缀
返回值string-array: 每次操作对应一个答案，且为文本

约束条件

1 ≤ ops.length ≤ 2000
words.length == ops.length
每个 ops[i] 都是 insert、search 或 startsWith。
1 ≤ words[i].length ≤ 20
words[i] 只包含小写英文字母。

示例

输入: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
输出: ["null", "false", "true", "null", "true"]
解释: car 是 card 的开头，因此 startsWith car 的结果是 "true"，但从未插入 car，所以第一次搜索结果是 "false"。插入 car 后，搜索就能找到它。

输入: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
输出: ["null", "null", "true", "false", "false", "true", "true"]
解释: 两个单词都以 te 开头，但都不完全等于 te，因此 startsWith 的结果是 "true"，search 的结果是 "false"。没有单词以 tex 开头，而 tea 是它自身的前缀。

输入: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
输出: ["false", "false", "null", "true", "false", "true"]
解释: 在空字典树中，这两个查询的结果都是 "false"。执行 insert dog 后，搜索可以找到它，没有单词以 dogs 开头，而 dog 以 do 开头。

进阶

如何添加一个 countPrefix p 操作，在 O(L) 时间内返回以 p 开头的不同已存储单词的数量？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

哈希集合可以回答 search 查询，但它没有起始位置的概念，所以 startsWith 会扫描每个单词。前缀树将每个单词存储为从根节点出发的一条字母路径：开头相同的单词会共享路径，并用一个标记表示存储的单词在哪里结束。这两种查询都只需沿路径遍历一次，最多经过 L 条边。

保存一个单词列表并扫描它

思路

将插入的每个单词都保存在列表中。search w 会将 w 与每个已存储的单词进行比较，而 startsWith p 会检查是否有已存储的单词以 p 开头。这样做是正确的，因为它直接检验了定义。存储了 n 个单词时，每次查询最多需要进行 n 次比较，每次比较最多涉及 L 个字母：1,000 个单词和 1,000 次查询会产生一百万次字符串比较。

算法

从一个空列表开始。
insert w：追加 w。
search w：返回是否有某个已存储的单词等于 w。
startsWith p：返回是否有某个已存储的单词以 p 开头。

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

前缀树：子节点链接和结束标记

思路

每个节点代表一个前缀，也就是从根节点到该节点路径上的字母。每个节点都会为可能接在后面的每个字母保存一个子节点链接（26 个槽位或一个映射），还有一个标志 isEnd，用于表示存储的单词是否恰好在此处结束。插入 tea 会创建 t、te 和 tea 对应的节点；之后插入 ten 时，只会新增 ten，因为这两个单词共享 te 对应的路径。

遍历时遇到缺失的链接，就能确定没有存储的单词以这些字母开头：tex 会在 te 处停止，因为那里没有指向 x 的链接。遍历到末尾时，当前位置就是查询内容对应的节点，因此 startsWith 为 true，而 search 会根据标志给出答案。te 对应的节点存在，但它的标志未开启，所以 search te 的结果为 false。无论存储了多少个单词，每次操作最多沿着 L 个链接遍历，而字典树中每个不同的前缀对应一个节点。

算法

创建一个没有子链接且 isEnd 关闭的根节点。
insert w：从根节点开始，沿着每个字母对应的链接前进；如果链接不存在，就创建节点。将最后一个节点的 isEnd 设为开启。
find(p)：从根节点开始，沿着每个字母对应的链接前进；如果某个链接不存在，立即返回空，否则返回到达的节点。
search w：当 find(w) 返回的节点已设置 isEnd 时，结果为 true。
startsWith p：当 find(p) 返回一个节点时，结果为 true。

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

易错点和边界情况

只要路径存在，就让 search 返回 true。插入 insert card 后，car 的路径存在，但 search car 必须返回 false。
只在新创建的节点上设置 isEnd。在 cards 后插入 card 时不会创建任何节点，但最后一个节点仍需要设置标记。
链接已存在时仍创建一个新的子节点。插入 ten 时创建新的 t 节点会导致 tea 丢失。
读取路径时越过末尾。只存储了 sun 时，startsWith sunny 必须在遇到第一个缺失的链接时停止，并返回 false。

常见问题3

字典树的时间复杂度是多少？

插入、搜索和 startsWith 每个操作都要沿着每个字母对应的一条链接前进，因此对于长度为 L 的单词，每个操作都需要 O(L)，与存储的单词数量无关。空间复杂度为 O(T)，其中有 T 个已插入的字母节点，每个节点最多有 26 条子链接。

为什么使用字典树而不是哈希集合？

哈希集合可以在 O(L) 时间内查找完整单词，但如果不扫描每个单词，就无法回答前缀查询。将每个前缀存入另一个集合，仅存储一个 20 个字母的单词就需要 210 个字母。Trie 会将每个共享前缀只存储一次，并通过一次遍历回答这两个问题。

Trie 节点应该使用包含 26 个链接的数组，还是哈希映射？

数组通过一个索引查找子节点，但每个节点要占用 26 个槽位，即使节点只有一个子节点也是如此。映射只存储实际存在的子节点，适用于任何字母表，但每个字母都要计算哈希值。对于小写英文字母，两种方式都可行；对于 Unicode 或稀疏的前缀树，映射更省内存。

def trieOps(ops, words):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

预期输出

["null", "false", "true", "null", "true"]