Trie structure and node implementation
Two implementation choices: (1) children as a dict (flexible, handles any character set) vs children as a list of 26 (faster access, fixed to lowercase letters). For interviews, use a dict — it is more readable and handles edge cases. The is_end flag is what distinguishes a complete word from a mere prefix. "app" and "apple" both exist in the trie, but only "apple" would have is_end=True at the "e" node if only "apple" was inserted.
Code template
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isEnd;
}
class Trie {
private final TrieNode root = new TrieNode();
}struct TrieNode {
unordered_map<char, TrieNode*> children;
bool isEnd = false;
};
class Trie {
TrieNode* root = new TrieNode();
};Insert, search, and startsWith templates
These three methods are identical except for the return condition at the end. Practice writing all three from memory — LC 208 asks for exactly this.
Code template
def insert(self, word):
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):
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):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return Truepublic void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return true;
}void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) node->children[c] = new TrieNode();
node = node->children[c];
}
node->isEnd = true;
}
bool search(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return node->isEnd;
}
bool startsWith(const string& prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return true;
}Word Search II — combining Trie with DFS (LC 212)
Word Search II is the most complex Trie problem in interviews. Build a Trie from all words in the dictionary. Then run DFS on the grid from each cell, traversing the Trie simultaneously with the grid traversal. When you reach an is_end=True node, record the word. The key optimization: instead of searching the grid for each word independently (O(W * 4^L)), you search the grid once and prune branches where no Trie path exists (O(R * C * 4^L) total, much better in practice). Mark is_end=False after finding a word to avoid duplicates. This pattern — Trie as a search guide for another traversal — appears in several advanced problems.
Wildcard search: Add and Search Words (LC 211)
When a search pattern contains "." (match any character), you cannot follow a single Trie path — you must branch to all children at that position. The recursion handles dots by trying all children. This DFS approach generalizes to regex-like matching in Tries.
Code template
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
if word[i] == ".":
return any(dfs(child, i + 1) for child in node.children.values())
if word[i] not in node.children:
return False
return dfs(node.children[word[i]], i + 1)
return dfs(self.root, 0)public boolean search(String word) {
return dfs(root, word, 0);
}
private boolean dfs(TrieNode node, String word, int i) {
if (i == word.length()) return node.isEnd;
char c = word.charAt(i);
if (c == '.') {
for (TrieNode child : node.children.values()) {
if (child != null && dfs(child, word, i + 1)) return true;
}
return false;
}
if (!node.children.containsKey(c)) return false;
return dfs(node.children.get(c), word, i + 1);
}bool search(const string& word) {
return dfs(root, word, 0);
}
bool dfs(TrieNode* node, const string& word, int i) {
if (i == word.size()) return node->isEnd;
char c = word[i];
if (c == '.') {
for (auto& [ch, child] : node->children) {
if (dfs(child, word, i + 1)) return true;
}
return false;
}
if (!node->children.count(c)) return false;
return dfs(node->children[c], word, i + 1);
}Replace Words (LC 648) — Trie for shortest prefix
Given a dictionary of root words and a sentence, replace each word with its shortest root prefix from the dictionary. Naive approach: for each word, check all dictionary roots — O(W * D * L). Trie approach: insert all roots into a Trie, then for each word, traverse the Trie until you find an is_end node (the shortest root) or exhaust the word. O(W * L) total. This pattern — using a Trie to find the shortest matching prefix — appears in multiple interview problems.
Code template
def replace_words(self, dictionary, sentence):
trie = Trie()
for root in dictionary:
trie.insert(root)
result = []
for word in sentence.split():
node = trie.root
for i, char in enumerate(word):
if char not in node.children:
break
node = node.children[char]
if node.is_end:
word = word[:i + 1]
break
result.append(word)
return " ".join(result)public String replaceWords(List<String> dictionary, String sentence) {
Trie trie = new Trie();
for (String root : dictionary) trie.insert(root);
List<String> result = new ArrayList<>();
for (String word : sentence.split(" ")) {
TrieNode node = trie.root;
String replacement = word;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!node.children.containsKey(c)) break;
node = node.children.get(c);
if (node.isEnd) { replacement = word.substring(0, i + 1); break; }
}
result.add(replacement);
}
return String.join(" ", result);
}string replaceWords(const vector<string>& dictionary, string sentence) {
Trie trie;
for (const auto& root : dictionary) trie.insert(root);
istringstream iss(sentence);
vector<string> result;
string word;
while (iss >> word) {
TrieNode* node = trie.root;
string replacement = word;
for (int i = 0; i < (int)word.size(); i++) {
char c = word[i];
if (!node->children.count(c)) break;
node = node->children[c];
if (node->isEnd) { replacement = word.substr(0, i + 1); break; }
}
result.push_back(replacement);
}
string out;
for (size_t i = 0; i < result.size(); i++) {
if (i) out += " ";
out += result[i];
}
return out;
}Trie vs alternatives: when to choose which
Trie vs hash set: both O(L) for exact lookup, but Trie additionally supports O(L + K) prefix enumeration (where K is the count of matching words). Choose hash set for exact lookups, Trie when prefix queries matter. Trie vs sorted list + binary search: sorted list supports prefix queries via binary search (O(log N + K)), but insertion is O(N). Trie insertion is O(L). Choose Trie for dynamic dictionaries with frequent insertions and prefix queries. Trie vs suffix array: suffix arrays are more space-efficient for static text; Tries are better for dynamic word sets. In interviews, Tries are always the right answer for prefix/autocomplete problems — suffix arrays are almost never required.