Autocomplete
We'll cover the following
Given a prefix, list every dictionary word that starts with it.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
car0
card1
care2
careful3
cart4
cat5
catch6
cab7
dog8
dot9
dote10
door11
Type "ca" and suggest every word that starts with it. First walk down the prefix, then collect everything below.
1 / 12
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(P + S) | O(S) | P = prefix length to walk down, S = size of the subtree collected. |
In Python
def autocomplete(self, prefix):
node = self.root
for ch in prefix:
if ch not in node: return []
node = node[ch]
out = []
def dfs(n, s):
if '$' in n: out.append(s)
for ch in sorted(k for k in n if k != '$'): dfs(n[ch], s + ch)
dfs(node, prefix)
return outSummary: say it in the interview
- Walk down the prefix, one letter per step. Everything in the subtree below that node is a valid completion, so collect it with a depth-first walk. You never look at words that do not share the prefix.
- Time O(P + S), space O(S). P = prefix length to walk down, S = size of the subtree collected.