转载自：https://leetcode-cn.com/problems/implement-trie-prefix-tree/ 原题

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

插入字符串

我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

• 子节点存在。沿着指针移动到子节点，继续处理下一个字符。
• 子节点不存在。创建一个新的子节点，记录在children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。

重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

查找前缀

我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

• 子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
• 子节点不存在。说明字典树中不包含该前缀，返回空指针。

重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的isEnd为真，说明Trie中存在该string

代码

 1 class Trie {
 2 private:
 3     vector<Trie*> children;
 4     bool isEnd;
 5 
 6     Trie* searchPrefix(string prefix) {
 7         Trie* node = this;
 8         for (char ch : prefix) {
 9             ch -= 'a';
10             if (node->children[ch] == nullptr) {
11                 return nullptr;
12             }
13             node = node->children[ch];
14         }
15         return node;
16     }
17 
18 public:
19     Trie() : children(26), isEnd(false) {}
20 
21     void insert(string word) {
22         Trie* node = this;
23         for (char ch : word) {
24             ch -= 'a';
25             if (node->children[ch] == nullptr) {
26                 node->children[ch] = new Trie();
27             }
28             node = node->children[ch];
29         }
30         node->isEnd = true;
31     }
32 
33     bool search(string word) {
34         Trie* node = this->searchPrefix(word);
35         return node != nullptr && node->isEnd;
36     }
37 
38     bool startsWith(string prefix) {
39         return this->searchPrefix(prefix) != nullptr;
40     }
41 };

字典树的应用：

例题：https://leetcode-cn.com/problems/word-search-ii/

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

实现：

 1 from collections import defaultdict
 2 
 3 
 4 class Trie:
 5     def __init__(self):
 6         self.children = defaultdict(Trie)
 7         self.word = ""
 8 
 9     def insert(self, word):
10         cur = self
11         for c in word:
12             cur = cur.children[c]
13         cur.is_word = True
14         cur.word = word
15 
16 
17 class Solution:
18     def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
19         trie = Trie()
20         for word in words:
21             trie.insert(word)
22 
23         def dfs(now, i1, j1):
24             if board[i1][j1] not in now.children:
25                 return
26 
27             ch = board[i1][j1]
28 
29             now = now.children[ch]
30             if now.word != "":
31                 ans.add(now.word)
32 
33             board[i1][j1] = "#"
34             for i2, j2 in [(i1 + 1, j1), (i1 - 1, j1), (i1, j1 + 1), (i1, j1 - 1)]:
35                 if 0 <= i2 < m and 0 <= j2 < n:
36                     dfs(now, i2, j2)
37             board[i1][j1] = ch
38 
39         ans = set()
40         m, n = len(board), len(board[0])
41 
42         for i in range(m):
43             for j in range(n):
44                 dfs(trie, i, j)
45 
46         return list(ans)