LC 0211 [M] Design Add and Search Words Data Structure - ALawliet/algorithms GitHub Wiki
M = length of keys
N = number of keys
add time: O(M)
add space: O(M)
search time: O(M) well-defined, O(N*26^M) undefined
search space: O(1)
or
O(W x L) {OWL}
class TrieNode():
def __init__(self):
self.word = False
self.children = dict() # c => next descendant TrieNodes
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def addWord(self, word: str) -> None:
"""
Adds a word into the data structure.
"""
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = True
def dfs(self, node, word):
for i, c in enumerate(word):
# recurse all the way down a path to see if we can match
# this has to come first, for example if '.' but no c in children
if c == '.':
for neighbor in node.children.values():
if self.dfs(neighbor, word[i+1:]):
return True
return False
if c not in node.children:
return False
node = node.children[c]
return node.word
def search(self, word: str) -> bool:
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
return self.dfs(self.root, word)
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)