Implement Trie (Prefix Tree)
LeetCode 208 | Difficulty: Medium
MediumProblem Description
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
- `Trie()` Initializes the trie object.
- `void insert(String word)` Inserts the string `word` into the trie.
- `boolean search(String word)` Returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise.
- `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise.
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Constraints:
- `1 <= word.length, prefix.length <= 2000`
- `word` and `prefix` consist only of lowercase English letters.
- At most `3 * 10^4` calls **in total** will be made to `insert`, `search`, and `startsWith`.
Topics: Hash Table, String, Design, Trie
Approach
Hash Map
Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?
When to use
Need fast lookups, counting frequencies, finding complements/pairs.
Trie (Prefix Tree)
Build a tree where each edge represents a character, and paths from root represent prefixes. Enables O(L) prefix lookups where L is the word length.
When to use
Prefix matching, autocomplete, word search, longest common prefix.
Design
Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.
When to use
Implementing a data structure or system with specific operation time requirements.
String Processing
Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.
When to use
Anagram detection, palindrome checking, string transformation, pattern matching.
Solutions
Solution 1: C# (Best: 188 ms)
| Metric | Value |
|---|---|
| Runtime | 188 ms |
| Memory | 49.5 MB |
| Date | 2020-10-18 |
Solution
public class Trie
{
TrieNode root;
/** Initialize your data structure here. */
public Trie()
{
root = new TrieNode(' ');
}
/** Inserts a word into the trie. */
public void Insert(string word)
{
var current = root;
foreach (var c in word)
{
if(current == null || current.children[c-'a']==null)
current.children[c-'a'] = new TrieNode(c);
current = current.children[c-'a'];
}
current.isWord = true;
}
/** Returns if the word is in the trie. */
public bool Search(string word)
{
var current = root;
foreach (var c in word)
{
if(current==null || current.children[c-'a'] == null)
return false;
current = current.children[c-'a'];
}
return current.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix)
{
var current = root;
foreach (var c in prefix)
{
if (current == null || current.children[c - 'a'] == null)
return false;
current = current.children[c - 'a'];
}
return true;
}
}
public class TrieNode
{
public TrieNode[] children;
public char c;
public bool isWord;
public TrieNode(char c, bool isWord = false)
{
this.c = c;
this.isWord = isWord;
children = new TrieNode[26];
}
// you might need some extra values according to different cases
};
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.Insert(word);
* bool param_2 = obj.Search(word);
* bool param_3 = obj.StartsWith(prefix);
*/
📜 2 more C# submission(s)
Submission (2018-10-22) — 252 ms, N/A
public class Trie
{
private TrieNode root { get; set; }
/** Initialize your data structure here. */
public Trie()
{
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void Insert(string word)
{
var current = root;
foreach (var c in word)
{
if(!current.Children.ContainsKey(c))
{
current.Children.Add(c, new TrieNode());
}
current=current.Children[c];
}
current.IsWord = true;
current.Word = word;
}
/** Returns if the word is in the trie. */
public bool Search(string word)
{
var current = root;
foreach (var c in word)
{
if (!current.Children.ContainsKey(c))
{
return false;
}
current = current.Children[c];
}
return current.IsWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix)
{
var current = root;
foreach (var c in prefix)
{
if (!current.Children.ContainsKey(c))
{
return false;
}
current = current.Children[c];
}
return true;
}
}
public class TrieNode
{
public bool IsWord { get; set; }
public string Word { get; set; }
public Dictionary<char, TrieNode> Children { get; set; }
public TrieNode()
{
Children = new Dictionary<char, TrieNode>();
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.Insert(word);
* bool param_2 = obj.Search(word);
* bool param_3 = obj.StartsWith(prefix);
*/
Submission (2018-10-22) — 288 ms, N/A
public class Trie
{
private TrieNode root { get; set; }
/** Initialize your data structure here. */
public Trie()
{
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void Insert(string word)
{
var current = root;
foreach (var c in word)
{
if(!current.Children.ContainsKey(c))
{
current.Children.Add(c, new TrieNode());
}
current=current.Children[c];
}
current.IsWord = true;
current.Word = word;
}
/** Returns if the word is in the trie. */
public bool Search(string word)
{
var current = root;
foreach (var c in word)
{
if (!current.Children.ContainsKey(c))
{
return false;
}
current = current.Children[c];
}
return current.IsWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix)
{
var current = root;
foreach (var c in prefix)
{
if (!current.Children.ContainsKey(c))
{
return false;
}
current = current.Children[c];
}
return true;
}
}
public class TrieNode
{
public bool IsWord { get; set; }
public string Word { get; set; }
public Dictionary<char, TrieNode> Children { get; set; }
public TrieNode()
{
Children = new Dictionary<char, TrieNode>();
}
public TrieNode(string word)
{
this.Word = word;
this.IsWord = true;
Children = new Dictionary<char, TrieNode>();
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.Insert(word);
* bool param_2 = obj.Search(word);
* bool param_3 = obj.StartsWith(prefix);
*/
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Hash Map | $O(n)$ | $O(n)$ |
| Trie | $O(L × n)$ | $O(L × n)$ |
Interview Tips
Key Points
- Discuss the brute force approach first, then optimize. Explain your thought process.
- Hash map gives O(1) lookup — think about what to use as key vs value.
- Clarify the expected time complexity for each operation before choosing data structures.