Auto-Complete System
One of the most common applications of a trie is an auto-complete system. Given a prefix, we want to suggest all words in the dictionary that have that prefix. This can be done by first navigating to the node representing the prefix, then performing a DFS to collect all words from that node.
Algorithm:
1. Traverse the trie to the node representing the prefix.
2. If the prefix node is null, return empty list.
3. Perform DFS from that node, building words as we go.
4. Collect words when we encounter end-of-word nodes.
Java implementation for autocomplete:
public List autocomplete(String prefix) {
List results = new ArrayList<>();
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) return results; // no such prefix
curr = curr.children[idx];
}
dfs(curr, new StringBuilder(prefix), results);
return results;
}
private void dfs(TrieNode node, StringBuilder sb, List results) {
if (node.isEndOfWord) {
results.add(sb.toString());
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
sb.append((char) (i + 'a'));
dfs(node.children[i], sb, results);
sb.setLength(sb.length() - 1);
}
}
}
This forms the basis of features like search suggestions, command-line tab completion, and phone keyboards.
Two Minute Drill
- Autocomplete uses trie to suggest words matching a prefix.
- Navigate to prefix node, then DFS to collect all words.
- Time complexity depends on number of suggestions.
- Can be optimized with frequency data for ranking.
Need more clarification?
Drop us an email at career@quipoinfotech.com