676. 实现一个魔法字典

from typing import List


class MagicDictionary:

    def __init__(self):
        self.tire: dict[str, dict] = dict()

    def buildDict(self, dictionary: List[str]) -> None:
        for word in dictionary:
            cur = self.tire
            for ch in word:
                if ch not in cur:
                    cur[ch] = dict()
                cur = cur[ch]
            cur['#'] = dict()

    def search(self, searchWord: str) -> bool:
        def dfs(tire: dict, i: int, replaced: bool) -> bool:
            if i == len(searchWord) - 1:
                if replaced:
                    return searchWord[i] in tire and '#' in tire[searchWord[i]]
                else:
                    return any(c != searchWord[i] and '#' in tire[c] for c in tire.keys())

            if replaced:
                return searchWord[i] in tire and dfs(tire[searchWord[i]], i + 1, True)

            return any(dfs(tire[c], i + 1, c != searchWord[i]) for c in tire.keys())

        return dfs(self.tire, 0, False)