Design Add and Search Words Data Structure

lcpy gen -n 211   # by problem number
lcpy gen -s design_add_and_search_words_data_structure   # by problem name

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

from typing import Any


class WordDictionary:
    # Time: O(1)
    # Space: O(1)
    def __init__(self) -> None:
        self.root: dict[str, Any] = {}

    # Time: O(m) where m = len(word)
    # Space: O(m) for new word
    def add_word(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node["#"] = True

    # Time: O(n * 26^k) where n = len(word), k = number of dots
    # Space: O(n) for recursion stack
    def search(self, word: str) -> bool:
        def dfs(i: int, node: dict[str, Any]) -> bool:
            if i == len(word):
                return "#" in node

            char = word[i]
            if char == ".":
                return any(key != "#" and dfs(i + 1, node[key]) for key in node)
            else:
                return char in node and dfs(i + 1, node[char])

        return dfs(0, self.root)