Implement Trie (Prefix Tree)
Implementing Trie alias as Prefix Tree
A prefix tree (or trie) is a special tree structure that helps store and quickly find strings, making it useful for tasks like auto-complete or spell checking.
Here’s what the PrefixTree class does:
- PrefixTree(): Creates an empty prefix tree.
- insert(String word): Adds a word to the prefix tree.
- search(String word): Checks if a word exists in the tree. Returns true if the word is found, otherwise false.
- startsWith(String prefix): Checks if any word in the tree starts with a given prefix. Returns true if such a word exists, otherwise false.
Example 1:
Input:
["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"]
Output:
[null, null, true, false, true, null, true]
["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"]
Output:
[null, null, true, false, true, null, true]
Explanation:
- PrefixTree prefixTree = new PrefixTree();
- prefixTree.insert(“dog”);
- prefixTree.search(“dog”); // return true
- prefixTree.search(“do”); // return false
- prefixTree.startsWith(“do”); // return true
- prefixTree.insert(“do”);
- prefixTree.search(“do”); // return true
Constraints:
- 1 <= word.length, prefix.length <= 1000
- word and prefix are made up of lowercase English letters.
Implementing Trie(Prefix Tree) Solution
Recommendation for Time and Space Complexity – Aim for O(n) time for each function call and O(t) space, where n is the length of the string and t is the total number of nodes in the Trie.
Hints for solving problems
Hint 1 :
A Trie is a tree-like structure where each node represents a character and has child nodes for the next characters. Each node has a flag to indicate if it’s the end of a word. The root node is the starting point, and words are stored by linking nodes based on their prefixes.
Hint 2 :
To insert a word, start from the root and iterate through each character. If a character is missing, create a new node for it. Move to the next character until the end, and then mark the last node as the end of the word.
Hint 3 :
To search for a word, follow the characters through the Trie. If a character is missing or the end-of-word flag isn’t set at the last node, return false.
There are mainly 2 approach to solve this problem-
- Prefix Tree(Array) Method
- Prefix Tree(Hash Map) Method
1. Prefix Tree(Array) Method
This approach uses an array to represent child nodes of each Trie node, typically of size 26 for lowercase English letters.
- Each node maintains an array to store references to its child nodes and a flag to mark the end of a word.
- This method is space-efficient for fixed character sets but less flexible for larger or dynamic character ranges.
– Time complexity: O(n) for each function call.
– Space complexity: O(t)
where n is the length of the string and t is the total number of TrieNodes created in the Trie.
Code
C++
Java
Python
JavaScript
C++
class TrieNode {
public:
TrieNode* children[26];
bool endOfWord;
TrieNode() {
for (int i = 0; i < 26; i++) { children[i] = nullptr; } endOfWord = false; } }; class PrefixTree { TrieNode* root; public: PrefixTree() { root = new TrieNode(); } void insert(string word) { TrieNode* cur = root; for (char c : word) { int i = c - 'a'; if (cur->children[i] == nullptr) {
cur->children[i] = new TrieNode();
}
cur = cur->children[i];
}
cur->endOfWord = true;
}
bool search(string word) {
TrieNode* cur = root;
for (char c : word) {
int i = c - 'a';
if (cur->children[i] == nullptr) {
return false;
}
cur = cur->children[i];
}
return cur->endOfWord;
}
bool startsWith(string prefix) {
TrieNode* cur = root;
for (char c : prefix) {
int i = c - 'a';
if (cur->children[i] == nullptr) {
return false;
}
cur = cur->children[i];
}
return true;
}
};
Java
public class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean endOfWord = false;
}
public class PrefixTree {
private TrieNode root;
public PrefixTree() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (cur.children[i] == null) {
cur.children[i] = new TrieNode();
}
cur = cur.children[i];
}
cur.endOfWord = true;
}
public boolean search(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (cur.children[i] == null) {
return false;
}
cur = cur.children[i];
}
return cur.endOfWord;
}
public boolean startsWith(String prefix) {
TrieNode cur = root;
for (char c : prefix.toCharArray()) {
int i = c - 'a';
if (cur.children[i] == null) {
return false;
}
cur = cur.children[i];
}
return true;
}
}
Python
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.endOfWord = False
class PrefixTree:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
i = ord(c) - ord("a")
if cur.children[i] == None:
cur.children[i] = TrieNode()
cur = cur.children[i]
cur.endOfWord = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
i = ord(c) - ord("a")
if cur.children[i] == None:
return False
cur = cur.children[i]
return cur.endOfWord
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
i = ord(c) - ord("a")
if cur.children[i] == None:
return False
cur = cur.children[i]
return True
JavaScript
class TrieNode {
constructor() {
this.children = new Array(26).fill(null);
this.endOfWord = false;
}
}
class PrefixTree {
constructor() {
this.root = new TrieNode();
}
/**
* @param {string} word
* @return {void}
*/
insert(word) {
let cur = this.root;
for (let c of word) {
let i = c.charCodeAt(0) - 97;
if (cur.children[i] === null) {
cur.children[i] = new TrieNode();
}
cur = cur.children[i];
}
cur.endOfWord = true;
}
/**
* @param {string} word
* @return {boolean}
*/
search(word) {
let cur = this.root;
for (let c of word) {
let i = c.charCodeAt(0) - 97;
if (cur.children[i] === null) {
return false;
}
cur = cur.children[i];
}
return cur.endOfWord;
}
/**
* @param {string} prefix
* @return {boolean}
*/
startsWith(prefix) {
let cur = this.root;
for (let c of prefix) {
let i = c.charCodeAt(0) - 97;
if (cur.children[i] === null) {
return false;
}
cur = cur.children[i];
}
return true;
}
}
2. Prefix Tree(Hash Map) Method
This approach uses a hash map in each Trie node to store child nodes, where keys represent characters and values point to the corresponding child nodes. It is more flexible and memory-efficient for dynamic or sparse character sets, as it only stores nodes for existing characters.
- Time complexity: O(n) for each function call.
- Space complexity: O(t)
where n is the length of the string and t is the total number of TrieNodes created in the Trie.
Code
C++
Java
Python
JavaScript
C++
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool endOfWord = false;
};
class PrefixTree {
TrieNode* root;
public:
PrefixTree() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* cur = root;
for (char c : word) {
if (cur->children.find(c) == cur->children.end()) {
cur->children[c] = new TrieNode();
}
cur = cur->children[c];
}
cur->endOfWord = true;
}
bool search(string word) {
TrieNode* cur = root;
for (char c : word) {
if (cur->children.find(c) == cur->children.end()) {
return false;
}
cur = cur->children[c];
}
return cur->endOfWord;
}
bool startsWith(string prefix) {
TrieNode* cur = root;
for (char c : prefix) {
if (cur->children.find(c) == cur->children.end()) {
return false;
}
cur = cur->children[c];
}
return true;
}
};
Java
public class TrieNode {
HashMap<Character, TrieNode> children = new HashMap<>();
boolean endOfWord = false;
}
public class PrefixTree {
private TrieNode root;
public PrefixTree() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
cur.children.putIfAbsent(c, new TrieNode());
cur = cur.children.get(c);
}
cur.endOfWord = true;
}
public boolean search(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
if (!cur.children.containsKey(c)) {
return false;
}
cur = cur.children.get(c);
}
return cur.endOfWord;
}
public boolean startsWith(String prefix) {
TrieNode cur = root;
for (char c : prefix.toCharArray()) {
if (!cur.children.containsKey(c)) {
return false;
}
cur = cur.children.get(c);
}
return true;
}
}
Python
class TrieNode:
def __init__(self):
self.children = {}
self.endOfWord = False
class PrefixTree:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.endOfWord = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.endOfWord
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.children[c]
return True
JavaScript
class TrieNode {
constructor() {
this.children = new Map();
this.endOfWord = false;
}
}
class PrefixTree {
constructor() {
this.root = new TrieNode();
}
/**
* @param {string} word
* @return {void}
*/
insert(word) {
let cur = this.root;
for (let c of word) {
if (!cur.children.has(c)) {
cur.children.set(c, new TrieNode());
}
cur = cur.children.get(c);
}
cur.endOfWord = true;
}
/**
* @param {string} word
* @return {boolean}
*/
search(word) {
let cur = this.root;
for (let c of word) {
if (!cur.children.has(c)) {
return false;
}
cur = cur.children.get(c);
}
return cur.endOfWord;
}
/**
* @param {string} prefix
* @return {boolean}
*/
startsWith(prefix) {
let cur = this.root;
for (let c of prefix) {
if (!cur.children.has(c)) {
return false;
}
cur = cur.children.get(c);
}
return true;
}
}
