> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/201-400/208.-shi-xian-trie-qian-zhui-shu.md).

# 208.实现Trie(前缀树)

[208. 实现 Trie (前缀树)](https://leetcode.cn/problems/implement-trie-prefix-tree/)

Trie树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

![图片](https://3747312504-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LXItOiQMDgh0S65YZXd%2Fuploads%2Fgit-blob-da5c326a157936d3ecf428aaa658d442224ab3ba%2F640.png?alt=media)

## 一、二维数组（不易理解）

* 使用二维数组`trie[]` 来存储所有的单词字符。
* 使用 `index`来自增记录到底用了多少个格子（相当于给被用到格子进行编号）。
* 使用 `count`数组记录某个格子被「被标记为结尾的次数」（当 `idx`编号的格子被标记了`n`次，则有 `count[idx]=n`）。

  如插入”apple“、”ape“后，trie数组、count数组如下：

  |   | a | b | c | d | e     | ... | l | ... | p     | ... | z | count\[i] |
  | - | - | - | - | - | ----- | --- | - | --- | ----- | --- | - | --------- |
  | 0 | 1 | 0 | 0 | 0 | 0     |     | 0 |     | 0     |     | 0 | 0         |
  | 1 | 0 | 0 | 0 | 0 | 0     |     | 0 |     | 2     |     | 0 | 0         |
  | 2 | 0 | 0 | 0 | 0 | **6** |     | 0 |     | **3** |     | 0 | 0         |
  | 3 | 0 | 0 | 0 | 0 | 0     |     | 4 |     | 0     |     | 0 | 0         |
  | 4 | 0 | 0 | 0 | 0 | 5     |     | 0 |     | 0     |     | 0 | 0         |
  | 5 | 0 | 0 | 0 | 0 | 0     |     | 0 |     | 0     |     | 0 | 1         |
  | 6 | 0 | 0 | 0 | 0 | 0     |     | 0 |     | 0     |     | 0 | 1         |

```python
class Trie:

    def __init__(self):
        self.N = 100000
        # 存储所有字符
        self.trie = [[0] * 26 for _ in range(self.N)]
        self.count = [0] * self.N
        self.index = 0
    
    # 实现插入
    def insert(self, word: str) -> None:
        # 横轴表示格子，纵轴表示字符
        # trie[i][j]表示要匹配的下一个格子序号
        i = 0	# 格子从0开始
        for s in word:
            j = ord(s) - ord('a')
            # 格子为0表示没匹配过
            if self.trie[i][j] == 0:
                # 使用的格子数+1
                self.index += 1
                self.trie[i][j] = self.index
            i = self.trie[i][j]
        # 统计i处的格子作为结尾的个数
        self.count[i] += 1

    # 实现搜索
    def search(self, word: str) -> bool:
        i = 0
        for s in word:
            j = ord(s) - ord('a')
            # 格子为0表示没匹配过
            if self.trie[i][j] == 0:
                return False
            # 否则匹配下一位
            i = self.trie[i][j]
        # 最后看i处格子被作为结尾的次数，只要不是0，都说明该字符串存在
        return self.count[i] != 0

    # 查找字典中是否有以prefix为前缀的字符串
    def startsWith(self, prefix: str) -> bool:
        i = 0
        for s in prefix:
            j = ord(s) - ord('a')
            # 格子为0表示没匹配过
            if self.trie[i][j] == 0:
                return False
            # 否则匹配下一位
            i = self.trie[i][j]
        # 与search函数的区别是，没有False，就是True
        return True
```

## 二、TrieNode（推荐）

定义数据结构TrieNode，是一个26叉树

```python
# 数据结构，Trie树节点，表示一个字符
class TrieNode:
    def __init__(self):
        self.end = False	# 标志该字符是否为某个单词的结尾
        self.tns = [None] * 26	#记录该字符的后续字符，26个分支表示a-z，None表示无后续

class Trie:

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


    def insert(self, word: str) -> None:

        i = self.root
        for s in word:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                i.tns[j] = TrieNode()
            i = i.tns[j]
        i.end = True

    def search(self, word: str) -> bool:
        i = self.root
        for s in word:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                return False
            i = i.tns[j]
        return i.end

    def startsWith(self, prefix: str) -> bool:
        i = self.root
        for s in prefix:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                return False
            i = i.tns[j]
        return True
```