TrieProblem 5 of 6
Implement a Phone Directory
Problem Statement
Given a list of contacts (phone directory), for each prefix typed by the user, display all contacts that start with that prefix. As the user types each character of a query string, show suggestions from the directory.
Example:
Input:
contacts = ["gikw", "gims", "girl", "gir"]
query = "gir"
Output:
After typing 'g': ["gikw", "gims", "gir", "girl"]
After typing 'gi': ["gikw", "gims", "gir", "girl"]
After typing 'gir': ["gir", "girl"]
Explanation: At each step, we show all contacts matching the prefix typed so far.
Noob-Friendly Explanation
Think of your phone's contact search. When you open the search bar and type "J", it shows all contacts starting with J — "John", "Jane", "Jake". Then you type "Jo" and it narrows down to "John", "Joseph". Each new letter you type filters the list further.
We need to build exactly that! A Trie is perfect because it stores words by their prefixes. When the user types a prefix, we jump to that node in the Trie and collect ALL words below it.
Approach 1: Brute Force
Intuition
For each prefix the user types, loop through all contacts and check if they start with that prefix. Simple but slow for large directories.
Algorithm
- For each character the user types, build the prefix so far
- Scan through all contacts
- Collect contacts that start with the current prefix
- Display them
java
import java.util.*;
class Solution {
public static List<List<String>> phoneDirectory(String[] contacts, String query) {
List<List<String>> result = new ArrayList<>();
Arrays.sort(contacts); // sort for consistent output
String prefix = "";
for (int i = 0; i < query.length(); i++) {
prefix += query.charAt(i);
List<String> matches = new ArrayList<>();
for (String contact : contacts) {
if (contact.startsWith(prefix)) {
matches.add(contact);
}
}
result.add(matches);
}
return result;
}
public static void main(String[] args) {
String[] contacts = {"gikw", "gims", "girl", "gir"};
String query = "gir";
List<List<String>> result = phoneDirectory(contacts, query);
for (int i = 0; i < result.size(); i++) {
System.out.println("Prefix '" + query.substring(0, i + 1) + "': " + result.get(i));
}
}
}Complexity Analysis
- Time Complexity: O(N * L * Q) — For each of Q characters typed, scan N contacts of average length L
- Space Complexity: O(N * L) — Storing results
Approach 2: Optimal (Trie-Based Phone Directory)
Intuition
Build a Trie from all contacts. For each prefix typed, navigate to the corresponding Trie node and collect all words reachable from that node using DFS. This avoids scanning the entire contact list repeatedly.
Algorithm
- Insert all contacts into a Trie
- For each character in the query, move to the next Trie node
- From that node, do a DFS to collect all complete words
- If a character doesn't exist in the Trie, output empty list for the rest
java
import java.util.*;
class Solution {
static class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26];
isEndOfWord = false;
}
}
private static TrieNode root;
private static void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true;
}
private static void collectWords(TrieNode node, StringBuilder prefix, List<String> words) {
if (node == null) return;
if (node.isEndOfWord) {
words.add(prefix.toString());
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
prefix.append((char) ('a' + i));
collectWords(node.children[i], prefix, words);
prefix.deleteCharAt(prefix.length() - 1);
}
}
}
public static List<List<String>> phoneDirectory(String[] contacts, String query) {
root = new TrieNode();
for (String contact : contacts) {
insert(contact);
}
List<List<String>> result = new ArrayList<>();
TrieNode current = root;
StringBuilder prefix = new StringBuilder();
boolean noMatch = false;
for (int i = 0; i < query.length(); i++) {
char ch = query.charAt(i);
prefix.append(ch);
if (noMatch || current.children[ch - 'a'] == null) {
noMatch = true;
result.add(new ArrayList<>()); // no suggestions
continue;
}
current = current.children[ch - 'a'];
List<String> suggestions = new ArrayList<>();
collectWords(current, prefix, suggestions);
result.add(suggestions);
}
return result;
}
public static void main(String[] args) {
String[] contacts = {"gikw", "gims", "girl", "gir"};
String query = "gir";
List<List<String>> result = phoneDirectory(contacts, query);
for (int i = 0; i < result.size(); i++) {
System.out.println("Prefix '" + query.substring(0, i + 1) + "': " + result.get(i));
}
// Prefix 'g': [gikw, gims, gir, girl]
// Prefix 'gi': [gikw, gims, gir, girl]
// Prefix 'gir': [gir, girl]
}
}Complexity Analysis
- Time Complexity: O(N * L + Q * L) — O(N * L) to build the Trie, then for each query character we collect matching words
- Space Complexity: O(N * L * 26) — Trie storage with 26 children per node
Key Takeaways
- Trie = Perfect for Prefix Search: Navigating to a prefix node and doing DFS gives all matching words
- Early Termination: Once a character is not found in the Trie, all subsequent queries return empty
- Sorted Output: Since Trie children are indexed 0-25 (a-z), DFS naturally gives alphabetically sorted results
- Real-world Use: Phone contacts, search bar autocomplete, IDE code suggestions