Python trie solution, search using dfs
class WordDictionary:\n    # initialize your data structure here.\n    def __init__(self):\n        self.trie={}\n\n    # @param {string} word\n    # @return {v
    class WordDictionary:\n    # initialize your data structure here.\n    def __init__(self):\n        self.trie={}\n\n    # @param {string} word\n    # @return {void}\n    # Adds a word into the data structure.\n    def addWord(self, word):\n        trie=self.trie\n        for c in word:\n            if c not in trie:\n                trie[c]={}\n            trie=trie[c]\n        trie['#']='#'\n\n    # @param {string} word\n    # @return {boolean}\n    # Returns if the word is in the data structure. A word could\n    # contain the dot character '.' to represent any one letter.\n    def search(self,word,trie=None):\n        if trie==None:\n            trie=self.trie\n        if not word:\n            if '#' in trie:\n                return True\n            else:\n                return False\n        c=word[0]\n        if c=='.':\n            for cc in trie:\n                if cc!='#' and self.search(word[1:],trie[cc]):\n                    return True\n        elif c in trie:\n            return self.search(word[1:],trie[c])\n        return False
['Depth-First Search', 'Trie', 'Python']