✔️ [Python3] TRIE (っ•́｡•́)♪♬, Explained
UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.\n\nThe most efficient underlying data structure here would be t
**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**\n\nThe most efficient underlying data structure here would be the Trie. First of all, it will let us economize space by storing reusable prefixes instead of whole words. Second, the time complexity for the search will be defined by the length of the word and not by the number of words in the storage. The only downside I see here, when we search, we have to deal with `.` symbol which can signify any character and that means we have to remember all possible characters in the current level of the trie during the traversing. On every level of trie, we can have up to 26 letters, and considering the maximum word length is 500, in the case of search call with all `.` characters in the worst case, the algorithm can eat up 26^500 space in memory.\n\nTime: **O(N)** - for add and for search\nSpace: **O(26^N)** - for search\n\nRuntime: 220 ms, faster than **93.62%** of Python3 online submissions for Design Add and Search Words Data Structure.\nMemory Usage: 25.5 MB, less than **62.45%** of Python3 online submissions for Design Add and Search Words Data Structure.\n\n```\nclass WordDictionary:\n\n    def __init__(self):\n        self.trie = dict()\n\n    def addWord(self, word: str) -> None:\n        node = self.trie\n        for ch in word + \'\uD83C\uDF3B\':\n            if ch not in node:\n                node[ch] = dict()\n\n            node = node[ch]\n\n    def search(self, word: str) -> bool:\n        nodes = [self.trie]\n        for ch in word + \'\uD83C\uDF3B\':\n            newNodes = []\n            for node in nodes:\n                if ch == \'.\': \n                    newNodes += [v for v in node.values()]\n                elif ch in node: \n                    newNodes.append(node[ch])\n\n            if not newNodes:\n                return False\n\n            nodes = newNodes\n            \n        return True\n```\n\n*`\uD83C\uDF3B` - means end of the word*\n\n**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**
['Python3']