Implement a phone directory (prefix search)

Medium

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: [[]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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
}