> For the complete documentation index, see [llms.txt](https://1005281342.gitbook.io/code-porter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://1005281342.gitbook.io/code-porter/shu-ju-jie-gou/1-qian-zhui-shu.md).

# 前缀树

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

```python
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        # 初始化根节点
        self.root = dict()

        # 单词标识
        self.is_word = "*#is_word#*"

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        # 当前节点为根节点
        node = self.root
        for s in word:
            # 如果该字符不在node中则进行创建
            if s not in node.keys():
                node[s] = dict()
            # 移动当前节点
            node = node[s]
        # 标记这是一个单词
        node[self.is_word] = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        # 当前节点为根节点
        node = self.root
        for s in word:
            # 该字符不在节点中则说明该单词不在单词列表中
            if s not in node.keys():
                return False
            node = node[s]

        return self.is_word in node.keys()

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        # 当前节点为根节点
        node = self.root
        for s in prefix:
            # 该字符不在节点中则说明该单词不在单词列表中
            if s not in node.keys():
                return False
            node = node[s]

        return True
```

## [211. 添加与搜索单词 - 数据结构设计](https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/)

### dfs

```python
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = dict()
        self.is_word = "*#is_word#*"

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.root
        for c in word:
            if c not in node.keys():
                node[c] = dict()
            node = node[c]
        node[self.is_word] = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """

        def dfs(node, i):
            if node is True:
                return False

            if i == len(word):
                return self.is_word in node.keys()

            if word[i] in node.keys():
                return dfs(node[word[i]], i + 1)
            elif word[i] == ".":
                for k in node.keys():
                    if dfs(node[k], i + 1):
                        return True
                return False

            return False

        return dfs(self.root, 0)
```

### bfs

```python
from collections import deque


class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = dict()
        self.is_word = "*#is_word#*"

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.root
        for c in word:
            if c not in node.keys():
                node[c] = dict()
            node = node[c]
        node[self.is_word] = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        node = self.root
        dq = deque()
        dq.append((node, 0))
        while dq:
            node, i = dq.popleft()
            if node is True:
                continue
            if i == len(word):
                if self.is_word in node.keys():
                    return True
                else:
                    continue
            if word[i] in node.keys():
                dq.append((node[word[i]], i + 1))
            elif word[i] == '.':
                for k in node.keys():
                    dq.append((node[k], i + 1))
        return False
```


---

# 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://1005281342.gitbook.io/code-porter/shu-ju-jie-gou/1-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.