Implement Trie Prefix Tree 🧠
LeetCode Link: Implement Trie Prefix Tree
Difficulty: Medium
Problem Explanation 📝
Problem: LeetCode 208 - Implement Trie (Prefix Tree)
Description: Implement a trie with insert, search, and startsWith methods.
Intuition: A trie, also known as a prefix tree, is a tree-like data structure that stores a set of strings. Each node in the trie represents a prefix or a complete word. The trie allows efficient insertion, search, and prefix matching operations.
Approach:
- TrieNode:
- Define a TrieNode class that represents each node in the trie.
- Each TrieNode has an array of pointers to child nodes, representing the 26 lowercase letters of the English alphabet.
- Each TrieNode also has a boolean flag to indicate if it represents a complete word.
- Trie:
- Define a Trie class that contains the root of the trie.
- Implement the insert method to insert a word into the trie:
- Start from the root and iterate over each character in the word.
- For each character, check if the corresponding child node exists. If not, create a new node and link it to the current node.
- Move to the child node and repeat the process for the next character.
- After iterating through all characters, mark the last node as a complete word.
- Implement the search method to search for a word in the trie:
- Start from the root and iterate over each character in the word.
- For each character, check if the corresponding child node exists. If not, the word is not in the trie.
- Move to the child node and repeat the process for the next character.
- After iterating through all characters, check if the last node represents a complete word.
- Implement the startsWith method to check if there is any word in the trie that starts with the given prefix:
- Start from the root and iterate over each character in the prefix.
- For each character, check if the corresponding child node exists. If not, there are no words with the given prefix.
- Move to the child node and repeat the process for the next character.
- After iterating through all characters, return true, indicating that there are words with the given prefix.
⌛ Time Complexity:
- Insert: O(m), where m is the length of the word being inserted.
- Search: O(m), where m is the length of the word being searched.
- StartsWith: O(m), where m is the length of the prefix being checked.
💾 Space Complexity:
- The space complexity is O(n*m), where n is the number of words inserted into the trie and m is the average length of the words.
Solutions 💡
Cpp 💻
class TrieNode {
public:
bool isWord;
TrieNode *children[26];
TrieNode() {
isWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
TrieNode *root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode *node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isWord = true;
}
bool search(string word) {
TrieNode *node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isWord;
}
bool startsWith(string prefix) {
TrieNode *node = root;
for (char c : prefix) {
int index = c - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return true;
}
};
/*
class Trie {
private:
// Defining TrieNode Datatype
struct TrieNode {
// Can have 26 diffenet childen because thats the amt of alphabets
TrieNode *child[26];
// To check where the word ends
bool isWord;
//Constructor to initialise values
TrieNode() {
isWord = false;
for (auto &c : child)
c = nullptr;
}
};
// Root pointer
TrieNode *root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
// Pointer to point the character we insert in trie
TrieNode* current = root;
for(auto i: word) {
// index of the character i.e. a = 0, z = 25
int index = i - 'a';
if(current->child[index] == NULL)
current->child[index] = new TrieNode();
// Pointing current to the character we just inserted
current = current->child[index];
}
current->isWord = true;
}
bool search(string word) {
TrieNode *current = root;
for(auto i: word) {
int index = i - 'a';
// If the child isn't there, return false. Else keep going.
if(current->child[index] == NULL)
return false;
current = current->child[index];
}
// Will return true if it's a word
return current->isWord;
}
// Same code as search but here we dont need to check if its a word
bool startsWith(string prefix) {
TrieNode *current = root;
for(auto i: prefix) {
int index = i - 'a';
// If the child isn't there, return false. Else keep going.
if(current->child[index] == NULL)
return false;
current = current->child[index];
}
return true;
}
};
*/
Python 🐍
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)