Day 78 || Trie + DFS || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem :\n![image.png](https://assets.leetcode.com/users/images/45ddd666-115b-4cd2-acdb-35cb946e8c91_1679207569.355929.png)\n\n**The code implements a WordDictionary using a Trie data structure. The addWord() function inserts words into the Trie by traversing the tree level by level and creating new nodes as necessary. The search() function searches for a given word in the Trie. It calls a helper function searchHelper() which recursively traverses the Trie, checking each character of the word against the children of the current node.**\n\n**If the current character is a ".", the searchHelper() function recursively searches all children nodes, and returns true if any of them contain the remaining characters of the word. Otherwise, it continues the search along the appropriate child node based on the current character of the word. If the end of the word is reached, it returns whether the current node represents a complete word or not.**\n\n**In essence, the algorithm allows for searching words in a dictionary that may contain "." (wildcards) that can match any character.**\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem :\n1. Define a TrieNode class with a boolean flag \'isWordCompleted\' and an array \'children\' of TrieNode pointers, each representing a child node for a given character.\n2. Define a WordDictionary class that contains a TrieNode pointer \'root\' representing the root node of the trie.\n3. Implement the constructor for the WordDictionary class that initializes the root node to a new TrieNode object.\n4. Implement a function \'addWord\' that takes a string \'word\' as input and adds it to the trie. It starts at the root node and iterates through each character of the input word, checking if the corresponding child node exists. If the child node does not exist, a new TrieNode object is created and added as a child node. Once all the characters of the word have been added to the trie, the \'isWordCompleted\' flag of the final TrieNode is set to true.\n5. Implement a function \'searchHelper\' that takes a string \'word\', an integer \'index\' representing the current character index in the word, and a TrieNode pointer \'newRoot\' representing the current node being searched. The function recursively searches through the trie, checking if the current character in the word matches any child nodes of the current node. If the character is a \'.\', the function recursively searches all child nodes. If the end of the word is reached, the function returns true if the \'isWordCompleted\' flag of the final TrieNode is true.\n6. Implement a function \'search\' that takes a string \'word\' as input and returns a boolean representing whether or not the word is present in the trie. This function simply calls \'searchHelper\' with the input word, starting from the root node.\n\n**Overall, this algorithm represents a trie data structure that can be used to store and search for words efficiently.**\n<!-- Describe your approach to solving the problem. -->\n\n# Code :\n```C++ []\nclass TrieNode {\npublic:\n    TrieNode* children[26];\n    bool isWordCompleted;\n\n    TrieNode() {\n        memset(children, 0, sizeof(children));\n        isWordCompleted = false;\n    }\n};\n\nclass WordDictionary {\npublic:\n    TrieNode* root;\n    WordDictionary() {\n        root = new TrieNode();\n    }\n    \n    void addWord(string word) {\n        TrieNode* newRoot = root;\n        for (char ch : word) {\n            int alphabetIndex = ch - \'a\';\n            if (newRoot -> children[alphabetIndex] == NULL) {\n                newRoot -> children[alphabetIndex] = new TrieNode();\n            }\n            newRoot = newRoot -> children[alphabetIndex];\n        }\n        newRoot -> isWordCompleted = true;\n    }\n    \n    bool searchHelper(string word, int index, TrieNode* newRoot) {\n        if (index == word.length())\n            return newRoot -> isWordCompleted;\n        char ch = word[index];\n        if (ch == \'.\') {\n            for (int i = 0; i < 26; i++) {\n                if (newRoot -> children[i] != NULL && searchHelper(word, index + 1, newRoot -> children[i])) {\n                    return true;\n                }\n            }\n            return false;\n        }\n        else {\n            if (newRoot -> children[ch - \'a\'] == NULL) {\n                return false;\n            }\n            return (searchHelper(word, index + 1, newRoot -> children[ch - \'a\']));\n        }\n    }\n\n    bool search(string word) {\n        return searchHelper(word, 0, root);\n    }\n};\n\n/**\n * Your WordDictionary object will be instantiated and called as such:\n * WordDictionary* obj = new WordDictionary();\n * obj->addWord(word);\n * bool param_2 = obj->search(word);\n */\n```\n```Java []\nclass TrieNode {\n    TrieNode[] children;\n    boolean isWordCompleted;\n\n    TrieNode() {\n        children = new TrieNode[26];\n        isWordCompleted = false;\n    }\n}\n\nclass WordDictionary {\n    TrieNode root;\n\n    WordDictionary() {\n        root = new TrieNode();\n    }\n    \n    void addWord(String word) {\n        TrieNode newRoot = root;\n        for (char ch : word.toCharArray()) {\n            int alphabetIndex = ch - \'a\';\n            if (newRoot.children[alphabetIndex] == null) {\n                newRoot.children[alphabetIndex] = new TrieNode();\n            }\n            newRoot = newRoot.children[alphabetIndex];\n        }\n        newRoot.isWordCompleted = true;\n    }\n    \n    boolean searchHelper(String word, int index, TrieNode newRoot) {\n        if (index == word.length())\n            return newRoot.isWordCompleted;\n        char ch = word.charAt(index);\n        if (ch == \'.\') {\n            for (int i = 0; i < 26; i++) {\n                if (newRoot.children[i] != null && searchHelper(word, index + 1, newRoot.children[i])) {\n                    return true;\n                }\n            }\n            return false;\n        }\n        else {\n            if (newRoot.children[ch - \'a\'] == null) {\n                return false;\n            }\n            return searchHelper(word, index + 1, newRoot.children[ch - \'a\']);\n        }\n    }\n\n    boolean search(String word) {\n        return searchHelper(word, 0, root);\n    }\n}\n\n```\n```Python []\nclass TrieNode:\n    def __init__(self):\n        self.children = [None] * 26\n        self.isWordCompleted = False\n\nclass WordDictionary:\n    def __init__(self):\n        self.root = TrieNode()\n    \n    def addWord(self, word: str) -> None:\n        newRoot = self.root\n        for ch in word:\n            alphabetIndex = ord(ch) - ord(\'a\')\n            if newRoot.children[alphabetIndex] is None:\n                newRoot.children[alphabetIndex] = TrieNode()\n            newRoot = newRoot.children[alphabetIndex]\n        newRoot.isWordCompleted = True\n    \n    def searchHelper(self, word: str, index: int, newRoot: TrieNode) -> bool:\n        if index == len(word):\n            return newRoot.isWordCompleted\n        ch = word[index]\n        if ch == \'.\':\n            for i in range(26):\n                if newRoot.children[i] is not None and self.searchHelper(word, index + 1, newRoot.children[i]):\n                    return True\n            return False\n        else:\n            alphabetIndex = ord(ch) - ord(\'a\')\n            if newRoot.children[alphabetIndex] is None:\n                return False\n            return self.searchHelper(word, index + 1, newRoot.children[alphabetIndex])\n\n    def search(self, word: str) -> bool:\n        return self.searchHelper(word, 0, self.root)\n\n```\n\n# Time Complexity and Space Complexity:\n- **Time complexity :**\n\nThe time complexity of the addWord function is O(k), where k is the length of the word being added. This is because we are traversing through the characters of the word and creating new nodes in the Trie for each character. Therefore, the total time complexity of adding n words of total length m is O(m*n).\n\nThe time complexity of the search function depends on the length of the input word and the size of the Trie. In the worst case, we have to search through all the nodes of the Trie, which is O(26^k), where k is the length of the input word. Therefore, the time complexity of the search function is O(26^k), where k is the length of the input word.\n\nHowever, in the best case, we can return early if the prefix of the input word does not exist in the Trie, which can reduce the time complexity significantly. Moreover, if the input word contains \'.\', we need to search through all possible child nodes of the current node, which is 26 in this case. Therefore, the actual time complexity of the search function can be much less than the worst-case scenario.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity :**\n\nThe space complexity of the Trie is O(nm), where n is the number of words and m is the average length of the words. This is because we are creating a new node for each character of each word. Therefore, the total number of nodes in the Trie is proportional to nm. However, in the worst case, when all the words have no common prefix, the space complexity can be as high as O(26^m), where m is the length of the longest word. Therefore, the space complexity of the Trie depends on the input data and can be very high in certain cases.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Depth-First Search', 'Trie', 'C++', 'Java', 'Python3']