Python: Trie+DFS
The idea:\n\n1. Create a trie from words. O(|words| \ max_word_len)\n2. Check each combination in the trie of the search_word with 1 char skipped. O(25\max_word
The idea:\n\n1. Create a trie from words. O(|words| \\* max_word_len)\n2. Check each combination in the trie of the search_word with 1 char skipped. O(25\\*max_word_len^2) \nExclude from the search the exact search_word if it is present in the original dict\n\ne.g.\n```\nsearch_word=hello, dict: hello, hullo\n\n_ello -> False, because this is search_word=dict[0] and requirements is - need 1 char different\nh_llo -> True. We need to skip h[e]llo (0 diff) combination here and find h[u]llo (1 diff from the search_word)\nhe_lo -> False\nhel_o -> False\nhell_ -> False\n```\n\n```\nclass Node(object):\n    def __init__(self):\n        self.children = {}\n        self.is_word = False\n\nclass MagicDictionary:\n    def __init__(self):\n        self.root = Node()\n\n    def buildDict(self, dictionary: List[str]) -> None:\n        # O(|words| * len(word))\n        for w in dictionary:\n            node = self.root\n            for c in w:\n                if c not in node.children:\n                    node.children[c] = Node()\n                node = node.children[c]\n            node.is_word = True\n\n    def search(self, search_word: str) -> bool:\n        def find(idx, node, skip_idx, changes):\n            if idx == n:\n                return node.is_word and changes == 1\n\n            # skip one letter in search_word\n            if skip_idx == idx:\n                for c in node.children:\n                    # avoid finding the same search_word in the dict\n                    if c != search_word[skip_idx]:\n                        if (find(idx + 1, node.children[c], skip_idx, changes + 1)):\n                            return True\n            # find the next letter in search_word\n            elif search_word[idx] in node.children:\n                return find(idx + 1, node.children[search_word[idx]], skip_idx, changes)\n            \n            # search_word next letter was not found in the trie\n            return False\n\n        # O(25*n^2), where n = len(search_word)\n        n = len(search_word)\n        for skip_idx in range(n):\n            # O(25*n), where n = len(search_word)\n            if find(0, self.root, skip_idx, 0):\n                return True\n            \n        return False\n```\n
['Depth-First Search', 'Trie', 'Python']