[Python] GENERIC SOLUTION TEMPLATE FOR ALL TRIE PROBLEMS
\n## RC ##\n## APPROACH : TRIE + DFS ## (BFS/DFS both are same here)\n## LOGIC ##\n## 1. Build Trie with give Words ##\n## 2. When there is character match next
```\n## RC ##\n## APPROACH : TRIE + DFS ## (BFS/DFS both are same here)\n## LOGIC ##\n## 1. Build Trie with give Words ##\n## 2. When there is character match next level will be only that characters children\n## 3. when ch = ".", we take it as, it matched all the children in curr row, so we send next children of those row ##\n## 4. When you are done with letters, check if it is end of word.\n\n## TIME COMPLEXITY: addWord: O(len(word)), search: O(N) ## (where N is the number of nodes in the Trie up to depth len(word))\n## SPACE COMPLEXITY : O(W) ##\n\nclass WordDictionary:\n    def __init__(self):\n        self.my_trie = Trie()\n        \n    def addWord(self, word: str) -> None:\n        self.my_trie.insert(word)\n\n    def search(self, word: str) -> bool:\n        return self.my_trie.serachWithDot(word)\n    \nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.endOfWord = False\n        \nclass Trie:\n    def __init__(self):\n        self.rootNode = TrieNode()\n        \n    # Inserts a word into the trie.\n    def insert(self, word: str) -> None:\n        currNode = self.rootNode\n        for idx, ch in enumerate(word):                     \n            if( ch not in currNode.children ):\n                currNode.children[ch] = TrieNode()          \n            currNode = currNode.children[ch]        # currnode.children[ch]\n        currNode.endOfWord = True\n    \n\t# Leetcode: 208, Implement Trie or Prefix Tree\n    # Returns if the word is in the trie.\n    def search(self, word: str) -> bool:\n        currNode = self.rootNode                    \n        for ch in word:\n            if(ch not in currNode.children):\n                return False\n            currNode = currNode.children[ch]\n        return currNode.endOfWord\n    \n\t# Leetcode: 648 Replace Words\n    # Returns if there is any word in the trie that starts with the given prefix.\n    def startsWith(self, prefix: str) -> bool:\n        currNode = self.rootNode                            \n        for ch in prefix:\n            if(ch not in currNode.children):\n                return False\n            currNode = currNode.children[ch]\n        return True\n    \n\t# Leetcode 211, Search words including "." (matches any character)\n    # Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter.\n    def serachWithDot(self, word: str) -> bool:\n            def dfs(currNode, word):\n                if not word:\n                    return currNode.endOfWord\n                ch = word[0]\n                if ch == ".":\n                    for node in [currNode.children[_] for _ in currNode.children]:\n                        if dfs(node, word[1:]):\n                            return True\n                else:\n                    if ch in currNode.children:\n                        if dfs(currNode.children[ch], word[1:]):\n                            return True\n                    else:\n                        return False\n            return dfs(self.rootNode, word)\n```
['Python', 'Python3']