Updated (22.12.23) | Python (faster than 99%, space efficient than 92%) Trie + Indexing
Updated (2022.12.23)\n\n\n\n\n\n\nThe recent problem Testcase has been changed, so it has been changed to Trie + Indexing + Queue.\nBeat 99.22% (Compute), 92.18
## Updated (2022.12.23)\n\n![image.png](https://assets.leetcode.com/users/images/b806db9d-1611-41f2-8740-3553e63a3234_1671734207.994404.png)\n\n![image.png](https://assets.leetcode.com/users/images/6343246c-e93e-4e12-ab33-805cf2f4ca04_1671734235.6923153.png)\n\n\nThe recent problem Testcase has been changed, so it has been changed to Trie + Indexing + Queue.\nBeat 99.22% (Compute), 92.18% (Memory).\n\nOptimization works as follows.\n- Exact match index cahing via Set $$O(1)$$\n- Guard clause based on string length $$O(1)$$\n- Otherwise search Trie from values indexed by word number $$O(L)$$\n- However, when a special search is included as in `\'.\'`, the BFS Trie branches through the queue. $$O(LlogL)$$\n\n```\nclass WordDictionary:\n    def __init__(self):\n        self.index = set()\n        self.words = defaultdict(dict)\n        \n    def addWord(self, word: str) -> None:\n        if word in self.index: return\n        self.index.add(word)\n        d = self.words[len(word)]\n        for c in word:\n            if c not in d: d[c] = {}\n            d = d[c]\n        \n    def search(self, word: str) -> bool:\n        if word in self.index: return True\n        \n        word_len = len(word)\n        if word_len not in self.words: return False\n        if word == \'.\' * word_len: return True\n        \n        ds = [self.words[word_len]]\n        for c in word:\n            nds = []\n            for d in ds:\n                if c == \'.\': nds += d.values()\n                elif c in d: nds.append(d[c])\n            ds = nds\n            \n        return bool(ds)\n```\n\n---\n\n## Previous content (2020.08.05)\n\nInitially, I write a code by using Trie among string search algorithms, but I realized that it was very inefficient in wildcard and applied index and generator.\n\nThe index consists of a total of 2 (word matching, count matching if only wild cards are used),\nIf the index is not hit, the word is fully scanned until it is matched.\n\nSometimes it shows that context-sensitive logic selection is more important than famous algorithms.\n\n```python\nclass WordDictionary:\n    def __init__(self):\n        self.index = {}\n        self.words = defaultdict(list)\n        \n    def compare(self, w1: str, w2: str) -> bool:\n        w1 = list(w1)\n        w2 = list(w2)\n        \n        while w1:\n            c1 = w1.pop(0)\n            c2 = w2.pop(0)\n            \n            if c1 == \'.\':\n                continue\n                \n            if c1 != c2:\n                return False\n            \n        return True\n        \n    def addWord(self, word: str) -> None:\n        self.index[word] = True\n        self.words[len(word)].append(word)\n        \n\n    def search(self, word: str) -> bool:\n        if word in self.index:\n            return True\n        \n        word_len = len(word)\n        if word_len not in self.words:\n            return False\n        \n        if word == \'.\' * word_len:\n            return True\n        \n        words = self.words[word_len]\n        for w in words:\n            if self.compare(word, w):\n                return True\n            \n        return False\n```
['Hash Table', 'Trie', 'Queue', 'Python']