秋招LeetCode刷题Day1 -- 前缀树专题

**秋招 LeetCode 刷题 Day1 -- 前缀树专题**

前缀树（Prefix Tree），也称为 trie， 是一种常见的数据结构。它是一棵多叉树，每个结点代表一个字符或一个字符串的前缀。前缀树在 LeetCode 中经常被用来解决字符串相关的问题。

###什么是前缀树？

前缀树是一种特殊的二叉树，每个结点都有三个孩子：左孩子、右孩子和子结点（也称为孩子）。每个结点代表一个字符或一个字符串的前缀。例如，给定一个字符串 "abc"，我们可以构建如下前缀树：

 a / 
 b c / 
 c

### 前缀树的应用前缀树有很多应用场景：

1. **自动补全**: 当用户输入一些字符时，可以使用前缀树来找到所有匹配的字符串。
2. **字符串匹配**: 可以使用前缀树来快速查找一个给定字符串是否存在于一组字符串中。
3. **字典查询**: 前缀树可以用来实现一个高效的字典查询系统。

### LeetCode 中的前缀树问题在 LeetCode 中，有很多题目涉及到前缀树。例如：

1. **Word Break II**：给定一个字符串和一个字典，要求找到所有可能的分割方案。
2. **Add and Search Word**: 给定一个字典和一个字符串，要求找到这个字符串是否存在于字典中。

### 前缀树的实现下面是一个简单的前缀树实现：

class TrieNode:
 def __init__(self):
 self.children = {}
 self.is_end_of_word = Falseclass Trie:
 def __init__(self):
 self.root = TrieNode()

 def insert(self, word: str) -> None:
 node = self.root for char in word:
 if char not in node.children:
 node.children[char] = TrieNode()
 node = node.children[char]
 node.is_end_of_word = True def search(self, word: str) -> bool:
 node = self.root for char in word:
 if char not in node.children:
 return False node = node.children[char]
 return node.is_end_of_word

###例子和注释下面是一个例子：

trie = Trie()
trie.insert("apple")
trie.insert("banana")

print(trie.search("apple")) # Trueprint(trie.search("banana")) # Trueprint(trie.search("orange")) # False

### 总结前缀树是一种常见的数据结构，经常被用来解决字符串相关的问题。在 LeetCode 中，有很多题目涉及到前缀树。通过理解前缀树的概念和实现，可以更好地解决这些问题。

**参考资料**

* [Wikipedia: Trie]( />* [LeetCode: Word Break II]( />* [LeetCode: Add and Search Word](