[Python] Trie solution with dfs, explained
In this problem, we need to use Trie data structure. For more details go to the problem 208. Implement Trie (Prefix Tree). \n\nSo, what we have here? \n1. TrieN
In this problem, we need to use **Trie** data structure. For more details go to the problem **208. Implement Trie (Prefix Tree)**. \n\nSo, what we have here? \n1. `TrieNode` class with two values: dictionary of children and flag, if this node is end of some word.\n2. Now, we need to implement `addWord(self, word)` function: we add symbol by symbol, and go deepere and deeper in our Trie. In the end we note our node as end node.\n3. Now, about `search(self, word)` function. Here we use `dfs(node, i)` with backtracking, because we can have symbol `.` in our word (here `node` is link to Trie node and `i` is index of letter in `word`). So we need to check all options: we go to all possible children and call `dfs` recursively. If we found not `.`, but just some letter, we check if we have this letter as children, and if we have, we go deeper. If we are out of letters, that is `i == len(word)`, we return `True` if current `end_node` is equal to `1` and false in opposite case. Finally, we return `False` if we can not go deeper, but we still have letters.\n4. Now, we just return `dfs(self.root, 0)`.\n\n**Complexity**: Easy part is space complexity, it is `O(M)`, where `M` is sum of lengths of all words in our Trie. This is upper bound: in practice it will be less than `M` and it depends, how much words are intersected. The worst time complexity is also `O(M)`, potentially we can visit all our Trie, if we have pattern like `.....`. For words without `.`, time complexity will be `O(h)`, where `h` is height of Trie. For words with several letters and several `.`, we have something in the middle.\n\n```\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.end_node = 0\n        \nclass WordDictionary:\n    def __init__(self):\n        self.root = TrieNode()      \n\n    def addWord(self, word):\n        root = self.root\n        for symbol in word:\n            root = root.children.setdefault(symbol, TrieNode())\n        root.end_node = 1\n        \n    def search(self, word):\n        def dfs(node, i):\n            if i == len(word): return node.end_node\n               \n            if word[i] == ".":\n                for child in node.children:\n                    if dfs(node.children[child], i+1): return True\n                    \n            if word[i] in node.children:\n                return dfs(node.children[word[i]], i+1)\n            \n            return False\n    \n        return dfs(self.root, 0)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Backtracking', 'Depth-First Search', 'Trie']