class Node:
def __init__(self,lable=None, data=None):
self.lable = lable
self.data = data
self.children = dict()
def addChild(self, key, data = None):
if not isinstance(key, Node):
self.children[key] = Node(key, data)
else:
self.children[key.lable] = key
def __getitem__(self,key):
return self.children[key]
class Trie:
def __init__(self):
self.head = Node()
self.bottom = Node()
def __getitem__(self,key):
return self.head.children[key],self.bottom.children[key]
def add(self, word, pair):
current_node = self.head
word_finished = True
current_node_2 = self.bottom
pair_finished = True
for i in range(len(word)):
if word[i] in current_node.children:
current_node = current_node.children[word[i]]
else:
word_finished = False
break
if not word_finished:
while i < len(word):
current_node.addChild(word[i])
current_node = current_node.children[word[i]]
i+=1
for j in range(len(pair)):
if pair[j] in current_node_2.children:
current_node_2 = current_node_2.children[word[j]]
else:
pair_finished = False
break
if not pair_finished:
while j < len(pair):
current_node_2.addChild(pair[j])
current_node_2 = current_node_2.children[word[j]]
j+=1
def has_word(self, word):
if word == '':
return False
if word ==None:
raise ValueError('Trie.has_word require not null string')
current_node = self.head
exists = True
for letter in word:
if letter in current_node.children:
current_node = current_node.children[letter]
else:
exists = False
break
if exists:
if current_node.data == None:
exists = False
return exists
def start_with_prefix(self,prefix):
words = list()
if prefix == None:
raise ValueError('reqire not null prefix')
top_node = self.head
bot_node = self.bottom
for letter in prefix:
if letter in top_node.children:
top_node = top_node.children[letter]
else:
return words
if top_node == self.head:
queue = [node for key, node in top_node.children.iteritems()]
else:
queue = [top_node]
while queue:
current_node = queue.pop()
if current_node.data !=None:
words.append(current_node.data)
queue = [node for key, node in current_node.children.iteritems()]+queue
return words
def getData(self, word, pair):
if not self.has_word(word):
raise ValueError('{} not found in trie'.fromat(word))
current_node = self.head
for letter in word:
current_node = current_node[letter]
if not self.has_word(pair):
raise ValueError('{} not found in trie'.format(pair))
current_node_2 = self.bottom
for letter in pair:
current_node_2 = current_node_2[letter]
return current_node.data,current_node_2.data
if __name__ == '__main__'
trie = Trie()
words = 'hello goodbye help gerald gold tea ted team to too tom stan standard money'
for word in words.split():
trie.add(word,word)
print "'goodbye' in trie: ", trie.has_word('goodbye')
print trie.start_with_prefix('g')
print trie.start_with_prefix('to')
What I have tried:
please help me to fix it.
the error i have :
when i want to see the words that i entered with prefix there is nothing shown.
for example : i add ("go","move")
if i type that i want to see all words with 'g' prefix i must see go , move but it did not work.