Description
Support adding lowercase words and searching patterns where '.' matches exactly one letter. Additions return null.
Solution
def create_word_dictionary():
return {'root': {}}
def add_word(state, word):
node = state['root']
for c in word:
node = node.setdefault(c,{})
node['#'] = True
def search(state, word):
def walk(node, i):
if i == len(word):
return '#' in node
c = word[i]
if c == '.':
return any(walk(child,i+1) for key,child in node.items() if key != '#')
return c in node and walk(node[c],i+1)
return walk(state['root'],0)Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[["addWord","cat"],["search","c.t"],["search","ca"]]- Output
[null,true,false]
The dot matches a; ca is too short.
Example 2
- Input
[["search","."]]- Output
[false]
The empty dictionary has no match.
Example 3
- Input
[["addWord","a"],["search","."]]- Output
[null,true]
The dot matches the one stored letter.
Approach
Store words in a trie. Search follows a literal edge or explores every child for a dot.
Time & space
Insertion O(L); search O(26^L) upper bound, limited by stored trie nodes; O(S) storage and O(L) search stack. L is the word or pattern length; S is the total number of inserted characters.