198. Phone Directory - Autocomplete by Prefix

Given n contact names and q query prefixes, for each query print every contact name that starts with that prefix, sorted alphabetically and space-separated on one line (print 'None' if nothing matches). Print one line of output per query.

Input: The first line contains an integer n, followed by n lines each with one contact name. The next line contains an integer q, followed by q lines each with a prefix query. Output: For each query, print every matching contact name (sorted alphabetically, space-separated) on its own line, or 'None' if no contact matches.

1 <= n, q <= 10^5

Collecting matches in sorted order is naturally achievable by always exploring a trie node's children in alphabetical order during the downward exploration step - avoiding a separate, extra sorting pass after collection.

This is the autocomplete feature you see on your phone's contact search, built from scratch: given a list of names and a series of prefix queries, list every name that starts with each queried prefix. Brute force: For each query, scan every single contact name directly and check if it starts with the query prefix (a simple string-starts-with check), collecting and sorting the matches - this costs O(name length) per contact per query, which adds up if there are many queries against many contacts. Optimised: Building the trie once lets each query jump DIRECTLY to the exact node representing the prefix (in time proportional only to the prefix's own length), then explore just the relevant subtree beneath it - completely avoiding re-scanning contacts that don't even share the prefix at all, unlike the brute force which checks every single contact for every single query.

Insert all n contact names into a trie once, character by character, optionally marking end-of-word nodes and keeping each node's children in alphabetical order (e.g. indexed by letter). For each query, walk down the trie following the prefix's characters directly to the node representing that prefix (or determine no such node exists, printing 'None'), then do a depth-first traversal of that subtree collecting every complete word found beneath it, which comes out in alphabetical order for free thanks to the ordered children. This touches only the characters relevant to the prefix and its matches, never rescanning unrelated contact names. Time: O(total characters across all names) to build, O(prefix length + total matched characters) per query Space: O(total characters across all names)

Sort all n contact names alphabetically once up front. For each query prefix, use binary search to find the first position in the sorted list where a name could begin with that prefix (a lower-bound search), then scan forward from there collecting names while they continue to share the prefix, stopping as soon as a name no longer matches - since the list is already sorted, all matches for a given prefix are guaranteed to sit in one contiguous block and come out already in alphabetical order with no per-query sort needed. Time: O(n log n) preprocessing, O(log n + k) per query Space: O(n * L)

For each query prefix, scan through all n contact names and check whether each one starts with that prefix using a simple character-by-character comparison, collecting every match into a list. Sort the collected matches alphabetically and print them space-separated on one line (or 'None' if nothing matched). Since this repeats a full scan and sort for every one of the q queries, the work multiplies across queries and names. Time: O(q * n * L) plus O(q * k log k) for sorting matches (L = name length, k = matches per query) Space: O(n * L)

1. Build a trie from all the contact names. 2. For each query prefix, walk the trie along the prefix's characters to find the node representing 'everything after this prefix'. 3. From that node, explore every path downward, collecting every complete word (contact name) found beneath it. 4. Sort the collected matches alphabetically and print them, or print 'None' if the prefix's path doesn't even exist in the trie.

Time: Building the trie once takes time proportional to the total characters across all contacts; each query then takes time proportional to the prefix's length plus however many matching contacts and their lengths need to be collected and sorted. Space: Proportional to the total characters across all contact names, for the trie itself.

Test a prefix matching no contacts ('None'), a prefix matching all contacts, a prefix equal to a full contact name that is also a prefix of longer ones, and n, q up to 10^5 for performance.

Autocomplete is one of the most common REAL-WORLD applications of a trie mentioned in interviews - be ready to connect this exact exercise to genuine products (search bars, IDE code completion, phone contact search) you've personally used.