Autocomplete
Walk to the prefix's node, then explore every branch below it, collecting every word found. About 11 minutes.
Two phases
Think of a search box suggesting words as you type. First, walk the typed letters to find the prefix's node, exactly like the starts-with check. If the walk falls off, there is nothing to suggest.
Second, explore every path below that node. Whenever you reach an end marker, the prefix plus the letters walked since is one of the answers.
node = root
for c in prefix:
node = node[c] # walk to the prefix- found
- []
Phase 1: walk the prefix c → a. Everything that starts with "ca" lives below this node.
Keeping the order predictable
Visiting the children in alphabetical order, or sorting the collected list at the end, gives a predictable result: an autocomplete list that is always alphabetical, which is what learners and users expect.
Without that, the suggestions might come out in a different order on different runs, which would make answers hard to compare.
words = ["cat", "car", "cow"], prefix = "ca". What does autocomplete return?
- A["car", "cat"]
- B["car", "cat", "cow"]
Show the answer
["car", "cat"]. Both extend "ca"; "cow" doesn't and is outside the "ca" subtree entirely.
Autocomplete
words is a list of lowercase words. Return every word in words that starts with prefix, sorted alphabetically.
words = ["cat", "car", "cow"], prefix = "ca" → ["car", "cat"]
0 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length, prefix.length ≤ 20 · every word is lowercase a-z