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)