> 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树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

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

![图片](/files/VfV84L5iJ72xjuqIPBRk)

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

* 使用二维数组`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
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/201-400/208.-shi-xian-trie-qian-zhui-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.