Word Dictionary

https://leetcode.com/problems/design-add-and-search-words-data-structure/

Similar to trie. Can be implemented with trie.

class WordDictionary(defaultdict):
    def __init__(self):
        super().__init__(WordDictionary)
        self.is_end = False
 
    def __bool__(self):
        return bool(super())
 
    def addWord(self, word: str) -> None:
        node = self
        for c in word:
            node = node[c]
        node.is_end = True
 
    def search(self, word: str) -> bool:
        node = self
        for i, c in enumerate(word):
            if c == '.':
                return any(
                    node.search(prefix + word[i + 1:])
                    for prefix in node.keys()
                )
            if not (node := node.get(c)):
                return False
        return node.is_end

Similar to trie, addWord can be simplified.

Improved

class WordDictionary(dict):
    def addWord(self, word: str) -> None:
        reduce(lambda node, c: node.setdefault(c, {}), word, self)['$'] = True
 
    def search(self, word: str) -> bool:
        return self.search_helper(word + '$', self)
 
    def search_helper(self, word: str, node: dict) -> bool:
        for i, c in enumerate(word):
            if c == ".":
                return any(
                    self.search_helper(word[i + 1:], node)
                    for node in node.values() if node is not True
                )
            else:
                if not (node := node.get(c)):
                    return False
        return True