Phone Directory Hard 0 attempts

Phone Directory

Hard Tries Other

Given unique lowercase contacts and a query string, return one list of matching contacts for each successive non-empty prefix of the query. Sort each list lexicographically. If a prefix has no matches, its list is empty.

Input Format
Implement phoneDirectory(contacts, query). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
contacts = ["gforgeeks","geeksforgeeks"]
query = "ge"
Output
[["geeksforgeeks","gforgeeks"],["geeksforgeeks"]]

Example 2

Input
contacts = ["abc"]
query = "z"
Output
[[]]
Constraints
  • 1 <= contacts.length <= 20
  • 1 <= query.length, contacts[i].length <= 20
  • Contacts are unique lowercase English words; query contains lowercase letters.
Test Cases (2)
Case 1
Args: [["gforgeeks","geeksforgeeks"],"ge"] Expected: [["geeksforgeeks","gforgeeks"],["geeksforgeeks"]]
Case 2
Args: [["abc"],"z"] Expected: [[]]
Topics
Tries

Trie with Prefix Search

javascript
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||[]); node.words.push(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 × N log N × L) as a loose upper bound including sorting suggestion lists | Space: O(N × L + Q × N), including returned suggestions

Saved in this browser only. Private to you.

JavaScript