Search and prefix check
We'll cover the following
For each query, decide whether it is a full word, only a prefix of a word, or neither.
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.
"a"apply0
appl1
bath2
bar3
bats4
ba5
Follow the branch "a". Walked so far: a.
dictionary [apple, app, apply, apt, bat, bath, batch, bar]
1 / 28
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(L) | O(1) | One step per letter, independent of how many words are stored. |
In Python
def search(self, word):
node = self.root
for ch in word:
if ch not in node: return False
node = node[ch]
return '$' in node # False for a pure prefix
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node: return False
node = node[ch]
return TrueSummary: say it in the interview
- Follow the query letter by letter. If a branch is missing, nothing matches. If you reach the end, check the end-of-word flag: set means a full word, unset means only a prefix. Cost depends on the query length, not on how many words are stored.
- Time O(L), space O(1). One step per letter, independent of how many words are stored.