Python, DFS solution, beats 96% Time and 100% Space
The intuition behind this approach is to create a tree with nodes that hold characters. A path from the root node to a leaf node defines a string in the diction
The intuition behind this approach is to create a tree with nodes that hold characters. A path from the root node to a leaf node defines a string in the dictionary. \n\nWe define a structure called a letterNode that holds the current node\'s character value, the possible characters it can lead to, and whether it is a leaf node. \n\nOur MagicDictionary instance has one attribute, which is just the big daddy node that holds the start to all possible words. When we first build the dictionary, we iterate through all the words that are given to us, adding each string to a possible path. If the prefix of a string exists in Big Daddy\'s chlidren, then we continue down that path until the characters no longer match up. For example, if we first add hello, we get the tree:\n```\nbig_daddy -> \'h\' -> \'e\' -> \'l\' -> \'l\' -> \'o\'\n```\n\nwhere the node \'o\' is a leaf node. If we then have to add the words \'heklo\' and \'zaddy\', then we get the tree:\n\n```\n\t\t    \'h\' -> \'e\' -> \'l\' -> \'l\' -> \'o\'\n\t      /          \\\nbig_daddy             \'k\' -> \'l\' -> \'o\'\n          \\\n\t        \'z\' -> \'a\' -> \'d\' -> \'d\' -> \'y\'\n```\n\nWhen we search, we use a modified DFS algorithm. For each pass, we keep track of the current string, popping off the front value of the string and keep track of the number of characters modified to get to that node. For each node holding a char, we iterate through the child nodes, and if the child node and the current string have the same character in front, then we explore that node without decrementing the number of characters modified. If they don\'t have the same character in front, then we explore that node and decrement the number of characters modified. Our accept condition is if our current string is empty, the node we are at is a leaf node, and the number of characters to modify is equal to the number we needed to modify. Otherwise, we reject this path.\n\n```\nclass letterNode:\n    def __init__(self, char):\n        self.char = char\n        self.children = []\n        self.is_leaf = False\nclass MagicDictionary:\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.big_daddy = letterNode(None)\n    \n    def addString(self, parent, curr_str):\n        if len(curr_str) != 0:\n            new_path = True\n            for child in parent.children:\n                if child.char == curr_str[0] and not child.is_leaf:\n                    self.addString(child, curr_str[1:])\n                    new_path = False\n                    break\n            \n            if new_path:\n                new_node = letterNode(curr_str[0])\n                parent.children.append(new_node)\n                if len(curr_str) != 0:\n                    self.addString(new_node, curr_str[1:])\n        \n        else:\n            parent.not_end = False\n    \n    def buildDict(self, dict):\n        """\n        Build a dictionary through a list of words\n        """\n        for word in dict:\n            self.addString(self.big_daddy, word)\n        \n\n    def search(self, word):\n        """\n        Returns if there is any word in the trie that equals to the given word after modifying exactly one character\n        """\n        \n        def dfs(parent, curr_str, chars_left_to_modify):\n            if len(curr_str) == 0:\n                if chars_left_to_modify == 0:\n                    if len(parent.children) == 0:\n                        return True\n                    else:\n                        return False\n                else:\n                    return False\n            \n            for child in parent.children:\n                if child.char == curr_str[0]:\n                    if dfs(child, curr_str[1:], chars_left_to_modify):\n                        return True\n                else:\n                    if chars_left_to_modify > 0:\n                        if dfs(child, curr_str[1:], chars_left_to_modify-1):\n                            return True\n            \n            return False\n        \n        return dfs(self.big_daddy, word, 1)\n```
[]