Implement a phone directory (prefix search)
Problem
Given a list of contacts and a query string, return for each prefix of the query (its first 1, 2, … characters) the sorted list of matching contacts (an empty list if none match).
Example 1
Input: contacts = ["geeikistest", "geeksforgeeks", "geeksfortest"], query = "geeips" Output: g, ge, gee → all three; geei → [geeikistest]; geeip, geeips → []
Also asked as: Implement a Phone Directory
Test cases
Case 1
Input: ["geeikistest","geeksforgeeks","geeksfortest"], "geeips" Expected: [["geeikistest","geeksforgeeks","geeksfortest"],["geeikistest","geeksforgeeks","geeksfortest"],["geeikistest","geeksforgeeks","geeksfortest"],["geeikistest"],[],[]]
Case 2
Input: ["bob","bobby","al"], "bo" Expected: [["bob","bobby"],["bob","bobby"]]
Case 3
Input: ["x"], "y" Expected: [[]]
View solutionHide solution1 approach
1. Trie; DFS from the prefix node to list matches
Time O(L + matches)Space O(total chars)
Insert all contacts. For each successive prefix of a query, find its trie node and DFS to collect all words below it.
function phoneDirectory(contacts, query) { const root = { children: new Map(), end: false }; for (const name of contacts) { let node = root; for (const c of name) { if (!node.children.has(c)) node.children.set(c, { children: new Map(), end: false }); node = node.children.get(c); } node.end = true; } const collect = (node, prefix, out) => { if (node.end) out.push(prefix); for (const [c, child] of node.children) collect(child, prefix + c, out); }; const results = []; let node = root, prefix = ''; for (const c of query) { if (!node || !node.children.has(c)) { node = null; results.push([]); continue; } node = node.children.get(c); prefix += c; const out = []; collect(node, prefix, out); results.push(out.sort()); } return results; // one suggestion list per typed character}