def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curr = self.Trie
for i, w in enumerate(word):
if w == '.':
wizards = []
for k in curr.keys():
if k == '#':
continue
wizards.append(self.search(word[:i] + k + word[i + 1:]))
return any(wizards)
if w not in curr:
return False
curr = curr[w]
return "#" in curr
标准的前缀树搜索我也贴一下代码，大家可以对比一下：
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curr = self.Trie
for w in word:
if w not in curr:
return False
curr = curr[w]
return "#" in curr
关键点
前缀树（也叫字典树），英文名 Trie（读作 tree 或者 try）
代码
语言支持：Python3
Python3 Code：
关于 Trie 的代码:
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.Trie = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
curr = self.Trie
for w in word:
if w not in curr:
curr[w] = {}
curr = curr[w]
curr['#'] = 1
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curr = self.Trie
for i, w in enumerate(word):
if w == '.':
wizards = []
for k in curr.keys():
if k == '#':
continue
wizards.append(self.search(word[:i] + k + word[i + 1:]))
return any(wizards)
if w not in curr:
return False
curr = curr[w]
return "#" in curr
主逻辑代码：
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.trie = Trie()
def addWord(self, word: str) -> None:
"""
Adds a word into the data structure.
"""
self.trie.insert(word)
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.
"""
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)
