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)