Related Topics
Data Structure
1
/ \
2 3
/ \ / \
4 5 6 7
And the following tree is a complete binary tree:
1
/ \
2 3
/ \ /
4 5 6
class TrieNode:
def __init__(self):
self.children = [None]*26 # 26 is the number of letters in the English alphabet
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def _char_to_index(self, char):
return ord(char) - ord('a')
def insert(self, word):
node = self.root
for char in word:
index = self._char_to_index(char)
if not node.children[index]:
node.children[index] = TrieNode()
node = node.children[index]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
index = self._char_to_index(char)
if not node.children[index]:
return False
node = node.children[index]
return node is not None and node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
index = self._char_to_index(char)
if not node.children[index]:
return False
node = node.children[index]
return True
In this implementation, the TrieNode class represents each node in the Trie, which has an array of children (one for each letter in the alphabet) and a boolean flag is_end_of_word indicating if the node represents the end of a word. The Trie class contains the root node and methods for inserting, searching, and checking for words that start with a given prefix.
The insert method inserts a word into the Trie by iterating over its characters and creating new nodes as necessary. The search method looks for a word in the Trie by traversing its nodes, and returns True if the end of the word is reached and the is_end_of_word flag is set. The starts_with method checks if there are any words in the Trie that start with a given prefix by traversing the nodes for the prefix and returning True if the end of the prefix is reached.
The time complexity for all three operations is O(m), where m is the length of the word or prefix being searched/inserted. This makes the Trie an efficient data structure for string-related problems.
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.