字典樹(shù)
在計(jì)算機(jī)科學(xué)中嗤谚，Trie，又稱字典樹(shù)怔蚌、單詞查找樹(shù)或鍵樹(shù)巩步，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種桦踊。典型應(yīng)用是用于統(tǒng)計(jì)椅野，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)籍胯。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢時(shí)間鳄橘，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹(shù)高芒炼。
Trie的核心思想是空間換時(shí)間瘫怜，利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷以達(dá)到提高效率的目的。
它有3個(gè)基本性質(zhì)：
根節(jié)點(diǎn)不包含字符本刽，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符鲸湃。
從根節(jié)點(diǎn)到某一節(jié)點(diǎn)赠涮，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串暗挑。
每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同笋除。
############################################
回到這一題，創(chuàng)建了一種數(shù)據(jù)結(jié)構(gòu)wordNode炸裆，數(shù)據(jù)結(jié)構(gòu)包含一個(gè)字典垃它，和一個(gè)bool變量，初始化一個(gè)root,為wordNode類型變量烹看，然后遍歷word將字符加入到字典樹(shù)上
class wordNode():
def __init__(self):
self.children = {}
self.isEnd = False
class WordDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = wordNode()
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
node = self.root
for w in word:
if w in node.children:
node = node.children[w]
else:
node.children[w] = wordNode()
node = node.children[w]
node.isEnd = True
def search(self, word):
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
stack = [(self.root, word)]
while stack:
node, w = stack.pop()
if not w:
if node.isEnd:
return True
elif w[0] == '.':
for v in node.children.values():
stack.append((v, w[1:]))
else:
if w[0] in node.children:
stack.append((node.children[w[0]], w[1:]))
return False
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
dfs的做法
class wordNode():
def __init__(self):
self.children = {}
self.isEnd = False
class WordDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = wordNode()
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
node = self.root
for w in word:
if w in node.children:
node = node.children[w]
else:
node.children[w] = wordNode()
node = node.children[w]
node.isEnd = True
def search(self, word):
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
self.res = False
self.dfs(self.root, word)
return self.res
def dfs(self, root, word):
if not word:
if root.isEnd:
self.res =True
return
elif word[0] == '.':
for v in root.children.values():
self.dfs(v, word[1:])
else:
if word[0] in root.children:
self.dfs(root.children[word[0]], word[1:])
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
