[Python] Simple Trie + DFS Recursive Solution with Explanation
For the Trie implementation I am not creating another TrieNode class instead using a dictionary as node and for wordEnd I am using "~" == True, if "~" is presen
For the Trie implementation I am not creating another TrieNode class instead using a dictionary as node and for wordEnd I am using "~" == True, if "~" is present in dictionary then the word ends here, since dictionary only contains lower case english letters so it will not be a problem\n```\nclass MagicDictionary:\n    def __init__(self):\n        self.root = {}\n\n    def buildDict(self, dictionary) -> None:\n        for word in dictionary:\n            curr = self.root  #resetting curr to root\n            for letter in word:\n                if letter not in curr:\n                    curr[letter] = {}\n                curr = curr[letter]\n            curr["~"] = True  #to signify word end\n\n    def search(self, searchWord: str) -> bool:\n        return self._search(searchWord, self.root, 0, 0)\n\t\t\n    #I got the idea for this implementation from the knapsack pattern we use in dynamic programming\n\t#At every iteration we have two options either we choose the letter at index i or we skip it and choose any other letter from Trie marking diff as 1\n\t#we will try both options and keep the best result\n\t#but only if diff is 0 ,if diff is already 1 that means we have already changed a letter and now we can only choose letter at current index i, since we need exactly 1 different character\n\t\n    def _search(self, word, node, diff, i):\n        if i == len(word):\n            if "~" in node and diff == 1: return True  #since we need difference of exactly one character\n            else: return False\n        \n        res = False\n        if diff == 0:  \n            for letter in node:\n                if letter == word[i] or letter == "~": continue  #ignoring curr index and "~"\n                res = res or self._search(word, node[letter], diff+1, i+1)\n        \n        if word[i] in node:\n            res = res or self._search(word, node[word[i]], diff, i+1)  # using "or" so that if any of the recursive calls returns true res will be true\n                \n        return res\n```
['Depth-First Search', 'Trie', 'Python', 'Python3']