Python standard Trie Implementation using a TrieNode class
There are several excellent questions using Trie data structure at Leetcode. The implementations share great simiarlities. It is therefore useful to list (some 
There are several excellent questions using Trie data structure at Leetcode. The implementations share great simiarlities. It is therefore useful to list (some of) them here for a better comparision and understanding. The functions of inserting words and searching if a prefix or a word exists in the trie are standard. What makes it trickier is to use ```Depth First Search (DFS)``` to extract the entire words under certain constraint conditions. It takes some time to settle in eventually.  \n\n**421. Maximum XOR of Two Numbers in an Array**\n```\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.is_word = False\n\nclass Solution:\n    def __init__(self):\n        self.root = TrieNode()\n        \n    def insert_word(self, word):\n        node = self.root\n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n            node = node.children[ch]\n        node.is_word = True\n    \n    def opposite_bit(self, bit):\n        if bit == \'0\':\n            return \'1\'\n        elif bit == \'1\':\n            return \'0\'\n        \n    def find_max_xor(self, cand_num):\n        node = self.root\n        bit_num = bin(cand_num)[2:].zfill(32)\n        max_xor = \'\'\n        for bit in bit_num:\n            oppo_bit = self.opposite_bit(bit)\n            if oppo_bit in node.children:\n                max_xor += oppo_bit\n                node = node.children[oppo_bit]\n            else:\n                max_xor += bit\n                node = node.children[bit]\n\n        return int(max_xor, 2) ^ cand_num\n            \n    def findMaximumXOR(self, nums: List[int]) -> int:\n        # construct the trie\n        for num in nums:\n            bit_num = bin(num)[2:].zfill(32)\n            self.insert_word(bit_num)\n        \n        max_xor_num = float(\'-inf\')\n        for num in nums:\n            max_xor_num = max(max_xor_num, self.find_max_xor(num))\n            \n        return max_xor_num\n```\n**208. Implement Trie (Prefix Tree)** the generic implementation of the trie.\n```\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.is_word = False\n        \nclass Trie:\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.root = TrieNode()\n\n    def insert(self, word: str) -> None:\n        """\n        Inserts a word into the trie.\n        """\n        node = self.root\n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n            node = node.children[ch]\n        node.is_word = True\n       \n    def search(self, word: str) -> bool:\n        """\n        Returns if the word is in the trie.\n        """\n        node = self.root\n        for ch in word:\n            if ch not in node.children:\n                return False\n            node = node.children[ch]\n        return node.is_word\n            \n    def startsWith(self, prefix: str) -> bool:\n        """\n        Returns if there is any word in the trie that starts with the given prefix.\n        """\n        node = self.root\n        for ch in prefix:\n            if ch not in node.children:\n                return False\n            node = node.children[ch]\n        return True\n```\n\n**211. Add and Search Word - Data structure design**\n\n```\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.is_word = False\n\nclass WordDictionary:\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.root =  TrieNode()\n        \n\n    def addWord(self, word: str) -> None:\n        """\n        Adds a word into the data structure.\n        """\n        node = self.root\n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n            node = node.children[ch]\n            \n        node.is_word = True\n        \n\n    def search(self, word: str) -> bool:\n        """\n        Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter.\n        """\n        node = self.root\n        return self.dfs(node, 0, word)\n        \n    def dfs(self, node, index, word):\n        if len(word) == index:\n            return node.is_word\n        \n        if word[index] == \'.\':\n            for ch in node.children:\n                if self.dfs(node.children[ch], index + 1, word):\n                    return True\n                \n        if word[index] in node.children:\n            return self.dfs(node.children[word[index]], index + 1, word)\n        \n        return False\n```\n**676. Implement Magic Dictionary**\n```\nclass TrieNode:\n    def __init__(self):\n        self.children = dict()\n        self.is_word = False\n        \nclass MagicDictionary:\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.root = TrieNode()\n    \n    def insert_word(self, word):\n        node = self.root\n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n            node = node.children[ch]\n            \n        node.is_word = True\n\n    def buildDict(self, dict: List[str]) -> None:\n        """\n        Build a dictionary through a list of words\n        """\n        for word in dict:\n            self.insert_word(word)\n        \n    def search(self, word: str) -> bool:\n        """\n        Returns if there is any word in the trie that equals to the given word after modifying exactly one character\n        """\n        return self.dfs(self.root, 0, word, 0)\n    \n    def dfs(self, node, index, word, count): # count of mismatch\n        if count > 1:\n            return False\n        \n        if len(word) == index:\n            return node.is_word and count == 1\n        \n        for ch in node.children:\n            if self.dfs(node.children[ch], index + 1, word, count + (word[index] != ch)):\n                return True\n            \n        return False\n```\n\n**1268. Search Suggestions System**\n\n```\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.is_word = False\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n        \n    def insert(self, word):\n        node = self.root\n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n            node = node.children[ch]\n            \n        node.is_word = True\n        \n    def startsWith(self, prefix): # return top three matches if exist\n        node = self.root\n        top_three = []\n        for ch in prefix:\n            if ch not in node.children:\n                return []\n            node = node.children[ch]\n            \n        return self.dfs(node, prefix, [])\n            \n    \n    def dfs(self, node, prefix, words):\n        if node.is_word:\n            words.append(prefix)\n            \n        for ch in node.children:\n            self.dfs(node.children[ch], prefix + ch, words)\n        return words\n        \n        \nclass Solution:\n    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n        \n        products.sort()\n        trie = Trie()\n        for product in products:\n            trie.insert(product)\n        \n        res = []\n        for i in range(len(searchWord)):\n            res.append(trie.startsWith(searchWord[:i+1])[:3])\n            \n        return res\n```
[]