Description
Implement insert, exact search, and startsWith for lowercase words. Operation examples return null for insertions.
Solution
def create_trie():
return {'root': {}}
def insert(state, word):
node = state['root']
for c in word:
node = node.setdefault(c,{})
node['#'] = True
def find(state, word):
node = state['root']
for c in word:
if c not in node:
return None
node = node[c]
return node
def search(state, word):
node = find(state, word)
return node is not None and '#' in node
def starts_with(state, prefix):
return find(state, prefix) is not NoneExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[["insert","cat"],["search","ca"],["startsWith","ca"]]- Output
[null,false,true]
ca is a prefix of cat but not an inserted full word.
Example 2
- Input
[["insert","a"],["search","a"]]- Output
[null,true]
The inserted single letter is a complete word.
Example 3
- Input
[["search","z"],["startsWith","z"]]- Output
[false,false]
No path exists before insertion.
Approach
Follow one child per character and mark only complete inserted words as terminal.
Time & space
O(L) per operation; O(S) storage, where L is the query or inserted word length and S is the total number of inserted characters.