🔥Easy Solutions in Java 📝, Python 🐍, and C++ 🖥️🧐Look at once 💻
Intuition\n Describe your first thoughts on how to solve this problem. \nTo support the search of a string with dots, we can use a trie data structure. We will 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo support the search of a string with dots, we can use a trie data structure. We will traverse the trie in a depth-first manner, looking for a matching character or dot at each node. If we find a dot, we will recursively explore all child nodes. If we reach the end of the word and the last node is marked as the end of a word, we have found a match.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use a trie data structure to store the words. While adding a word to the trie, we can iterate through each character in the word and add it to the trie if it is not already present. We also mark the last node of the word as an end-of-word node. For searching a word in the trie, we traverse through each character of the word and see if it matches a character in the trie. If the character is a dot (.), we recursively search for the remaining part of the word in all the child nodes of the current node. If the character is not a dot, we traverse to the corresponding child node in the trie. If we reach the end of the word and the last node is an end-of-word node, then the word is present in the trie.\n\n\n\n\n# Complexity\n- Time complexity:\nThe time complexity for adding a word to the trie is O(n), where n is the length of the word. The time complexity for searching a word in the trie is O(n * m), where n is the length of the word and m is the number of nodes in the trie. However, the number of nodes in the trie is bounded by the total number of characters in all the words added to the trie, which is at most 26 * n * m. Therefore, the worst-case time complexity for searching a word in the trie is O(n * m).\n\n\n- Space complexity:\nThe space complexity of the trie is O(26 * n * m), where n is the maximum length of the words and m is the number of words in the trie. This is because each node in the trie has 26 children and each character in each word is represented by a node in the trie.\n\n\n\n\n\n![image.png](https://assets.leetcode.com/users/images/b427e686-2e5d-469a-8e7a-db5140022a6b_1677715904.0948765.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n```\n# Code\n``` Java []\nclass TrieNode {\n    boolean isEndOfWord;\n    TrieNode[] children;\n\n    public TrieNode() {\n        isEndOfWord = false;\n        children = new TrieNode[26];\n    }\n}\n\nclass WordDictionary {\n    private TrieNode root;\n\n    public WordDictionary() {\n        root = new TrieNode();\n    }\n\n    public void addWord(String word) {\n        TrieNode curr = root;\n        for (char c : word.toCharArray()) {\n            if (curr.children[c - \'a\'] == null) {\n                curr.children[c - \'a\'] = new TrieNode();\n            }\n            curr = curr.children[c - \'a\'];\n        }\n        curr.isEndOfWord = true;\n    }\n\n    public boolean search(String word) {\n        return searchHelper(word, 0, root);\n    }\n\n    private boolean searchHelper(String word, int index, TrieNode curr) {\n        if (index == word.length()) {\n            return curr.isEndOfWord;\n        }\n\n        char c = word.charAt(index);\n\n        if (c == \'.\') {\n            for (TrieNode child : curr.children) {\n                if (child != null && searchHelper(word, index + 1, child)) {\n                    return true;\n                }\n            }\n            return false;\n        } else {\n            TrieNode child = curr.children[c - \'a\'];\n            if (child == null) {\n                return false;\n            }\n            return searchHelper(word, index + 1, child);\n        }\n    }\n}\n\n\n```\n```Python []\nclass WordDictionary(object):\n    def __init__(self):\n        self.words = {}\n\n    def addWord(self, word):\n        """\n        :type word: str\n        :rtype: None\n        """\n        curr = self.words\n        for c in word:\n            if c not in curr:\n                curr[c] = {}\n            curr = curr[c]\n        curr[\'$\'] = True\n\n    def search(self, word):\n        """\n        :type word: str\n        :rtype: bool\n        """\n        return self.dfs(self.words, word)\n\n    def dfs(self, node, word):\n        if not word:\n            return \'$\' in node\n        c = word[0]\n        if c == \'.\':\n            for child in node:\n                if child != \'$\' and self.dfs(node[child], word[1:]):\n                    return True\n        elif c in node:\n            return self.dfs(node[c], word[1:])\n        return False\n\n\n```\n```C++ []\nclass TrieNode {\npublic:\n    bool isEndOfWord;\n    TrieNode* children[26];\n\n    TrieNode() {\n        isEndOfWord = false;\n        for (int i = 0; i < 26; i++) {\n            children[i] = nullptr;\n        }\n    }\n};\n\nclass WordDictionary {\nprivate:\n    TrieNode* root;\n\npublic:\n    WordDictionary() {\n        root = new TrieNode();\n    }\n\n    void addWord(string word) {\n        TrieNode* curr = root;\n        for (char c : word) {\n            if (curr->children[c - \'a\'] == nullptr) {\n                curr->children[c - \'a\'] = new TrieNode();\n            }\n            curr = curr->children[c - \'a\'];\n        }\n        curr->isEndOfWord = true;\n    }\n\n    bool search(string word) {\n        return searchHelper(word, 0, root);\n    }\n\n    bool searchHelper(string word, int index, TrieNode* curr) {\n        if (index == word.length()) {\n            return curr->isEndOfWord;\n        }\n\n        char c = word[index];\n\n        if (c == \'.\') {\n            for (int i = 0; i < 26; i++) {\n                if (curr->children[i] != nullptr && searchHelper(word, index + 1, curr->children[i])) {\n                    return true;\n                }\n            }\n            return false;\n        } else {\n            if (curr->children[c - \'a\'] == nullptr) {\n                return false;\n            }\n            return searchHelper(word, index + 1, curr->children[c - \'a\']);\n        }\n    }\n};\n\n\n\n```\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```
['String', 'Depth-First Search', 'Design', 'Trie', 'Java']