Add and Search Word
Design a data structure that supports adding new words and finding if a string matches any previously added string. Tags: Tree
Try It!
Discussion
Video
Solution
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.trie = {}
def addWord(self, word: str) -> None:
level = self.trie
for c in word:
if c not in level:
level[c] = {}
level = level[c]
level['#'] = '#'
def search(self, word: str) -> bool:
return self.helper(word, self.trie)
def helper(self, word, level):
if word == '':
return '#' in level
c = word[0]
if c == '.':
for pos_c in level:
if pos_c != '#' and self.helper(word[1:], level[pos_c]):
return True
return False
elif c not in level:
return False
else:
return self.helper(word[1:], level[c])
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)