节点法前缀树加DFS
class TrieNode(object):
def __init__(self):
self.children = [None]*26
self.flag = False
class WordDictionary(object):
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
"""
:type word: str
:rtype: None
"""
node = self.root
for i in word:
ch = ord(i)-ord("a")
if not node.children[ch]:
node.children[ch] = TrieNode()
node = node.children[ch]
node.flag = True
def search(self, word):
"""
:type word: str
:rtype: bool
"""
def dfs(index,node):
if len(word) == index:
return node.flag
ch = word[index]
if ch != ".":
child = node.children[ord(ch) - ord('a')]
if child is not None and dfs(index + 1, child):
return True
else:
for child in node.children:
if child is not None and dfs(index+1,child):
return True
return False
return dfs(0,self.root)
字典法前缀树加DFS
class TrieNode(object):
def __init__(self):
self.children = {}
self.flag = False
class WordDictionary(object):
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.flag = True
def search(self, word):
def dfs(index,node):
if not node:
return False
if index == len(word):
return node.flag
ch = word[index]
if ch != '.':
if ch not in node.children:
return False
node = node.children[ch]
return dfs(index+1,node)
else:
for child in node.children.values():
if dfs(index+1,child):
return True
return False
return dfs(0,self.root)