phone-directory Hard 0 attempts

phone-directory

Hard Tries Other

Design a phone directory which supports search(query) that returns contacts matching the given query prefix.

Example: contacts = ["gforgeeks","geeksforgeeks"], query = "ge" → ["geeksforgeeks","gforgeeks"] filtered by prefix

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 20
  • 1 <= query.length <= 20
Topics
Tries

Trie with Prefix Search

function phoneDirectory(contacts, query) {
  const trie = {};
  for (const c of contacts) {
    let node = trie;
    for (const ch of c) { if (!node[ch]) node[ch] = {}; node = node[ch]; node.words = (node.words||[]).concat(c); }
  }
  const results = [];
  let node = trie;
  for (let i = 0; i < query.length; i++) {
    node = node?.[query[i]];
    results.push(node?.words?.sort() || []);
  }
  return results;
}

Time: O(n × L + q × L) | Space: O(n × L)

Saved in this browser only. Private to you.

JavaScript