Python | DFS on a Trie | Notes
\n/*\nwe can approach this problem using trie. Problem is very similar to \nAdd and search word data structures.\nWe can create a standard trie and search for w
```\n/*\nwe can approach this problem using trie. Problem is very similar to \nAdd and search word data structures.\nWe can create a standard trie and search for words in that.\nif at all, we come across a character which is not present down the path,\nwe still continue to see if word is still searchable. If we are able to find the \nremaining word, we return True else we return False\n*/\n```\n```\nclass TrieNode():\n    def __init__(self):\n        self.end = False\n        self.children = {}\n        \nclass MagicDictionary:\n\n    def __init__(self):\n        self.root = TrieNode()\n\n    def buildDict(self, dictionary: List[str]) -> None:\n        def insert(index, root, word):\n            if index == len(word):\n                root.end = True\n                return\n            if word[index] not in root.children:\n                root.children[word[index]] = TrieNode()\n            insert(index+1, root.children[word[index]], word)\n        for word in dictionary:\n            insert(0, self.root, word)\n        \n    def search(self, searchWord: str) -> bool:\n        def search_fun(index, root, changed):\n            if index == len(searchWord):\n                if root.end and changed:\n                    return True\n                return False\n            if not changed:\n                for key, value in root.children.items():\n                    if key == searchWord[index]:\n                        continue\n                    if search_fun(index+1, value, True):\n                        return True\n            \n            if searchWord[index] not in root.children:\n                return False\n            else:\n                return search_fun(index+1, root.children[searchWord[index]], changed)\n        \n        return search_fun(0, self.root, False)\n```
['Depth-First Search', 'Trie', 'Python']