LeetCode #211：添加与搜索单词 - 数据结构设计
1970-01-01 00:00 (GMT+8) 阅读时间 0 分钟 面试算法LeetCodeLeetCode-MediumPython字典树Trie树（前缀树）DFS
https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/
题目分析
因为和字典相关，想到的自然就是树状结构。可以用一个 Trie 树来存储和检索单词。
Trie 树也叫前缀树，通过逐个匹配前缀来检索单词。
题解
这个解法效率有点低，不过能过，先这样吧。
python
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.isEnd = False
class Trie:
def __init__(self):
self.root = TrieNode()
def dfs(self, node, string, idx):
for i in range(idx, len(string)):
if string[i] == ".": # 默认该节点全匹配，递归检查所有子节点
for child in node.children:
if child is not None and self.dfs(child, string, i + 1):
return True
return False
else:
index = ord(string[i]) - ord("a")
if node.children[index] is None:
return False
node = node.children[index]
return node.isEnd
def search(self, string):
return self.dfs(self.root, string, 0)
def insert(self, string):
node = self.root
for letter in string:
index = ord(letter) - ord("a")
if node.children[index] is None:
node.children[index] = TrieNode()
node = node.children[index]
node.isEnd = True
class WordDictionary:
def __init__(self):
self.trie = Trie()
def addWord(self, word: str) -> None:
self.trie.insert(word)
def search(self, word: str) -> bool:
return self.trie.search(word)
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)