13.6 字典树

# 13.6 字典树

字典树（Trie）用于判断字符串是否存在或者是否具有某种字符串前缀。

图 13.1: 字典树，存储了单词 A、to、tea、ted、ten、i、in 和 inn，以及它们的频率

为什么需要用字典树解决这类问题呢？假如我们有一个储存了近万个单词的字典，即使我们使用哈希，在其中搜索一个单词的实际开销也是非常大的，且无法轻易支持搜索单词前缀。然而由于一个英文单词的长度 n 通常在 10 以内，如果我们使用字典树，则可以在 $$O(n)$$——近似 $$O(1)$$ 的时间内完成搜索，且额外开销非常小。

## [208. Implement Trie (Preﬁx Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)

### 题目描述

尝试建立一个字典树，支持快速插入单词、查找单词、查找单词前缀的功能。

### 输入输出样例

以下是数据结构的调用样例。

```
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // true
trie.search("app"); // false
trie.startsWith("app"); // true
trie.insert("app");
trie.search("app"); // true
```

### 题解

以下是字典树的典型实现方法。

```py
class Trie:
    def __init__(self):
        self.lookup = {}

def insert(self, word: str) -> None:
        tree = self.lookup
        for a in word:
            if a not in tree:
                tree[a] = {}
            tree = tree[a]
        tree["#"] = "#"

def search(self, word: str) -> bool:
        tree = self.lookup
        for a in word:
            if a not in tree:
                return False
            tree = tree[a]
        if "#" in tree:
            return True
        return False

def startsWith(self, prefix: str) -> bool:
        tree = self.lookup
        for a in prefix:
            if a not in tree:
                return False
            tree = tree[a]
        return True
```