Click here to Skip to main content
15,949,686 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Python
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__':
    """ Example use """
    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.
Posted
Updated 25-Aug-16 8:33am
v4
Comments
Patrice T 22-Aug-16 8:09am    
And you have plan to explain what is the problem ?
Akbar Fardi 22-Aug-16 8:11am    
i can't linked the word to its pair
Patrice T 22-Aug-16 8:19am    
give details like error message, position on error.
Use Improve question to update your question.
Akbar Fardi 22-Aug-16 8:30am    
ok

1 solution

Because Trie is supposed to inherit Node, but Python does not know that unless you tell it. Change your class statement to:
Python
class Trie(Node):

Also in future, when posting error messages with line numbers, please indicate in your source code which lines are being referenced. Trying to count down to 68 in the above code is extremely tedious.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900