[Java/C++/Python] A very well detailed EXPLANATION!
\nWhat the question is saying, \nWe have to design a data structure that supports adding new words and finding if a string matches any previously added string.\
```\nWhat the question is saying, \nWe have to design a data structure that supports adding new words and finding if a string matches any previously added string.\n```\n\n**So, to design a DS we only need to support 3 function\'s for this data structure.**\n\n* One is the **constructor** that\'s gonna intialize the object.\n* One is **Adding** the **word\'s**, but all of them are lower case from **a to z**\n* One is **Searching** a **word**, and the word can contains any character from **a - z**. But there is **1 additional character** it contains, **"."** character `[And what they told "." character is a wild card, can match any character easily in the string]`\n\n**The brute force way to solve this problem** is pretty simple, "*having a list of words & then just for every search we would just see, if this search match any of the word in input list*." **[But it\'s not an efficient way]**\n\nLet\'s talk about, **efficient way to solve this problem**. And for that we require **Trie data structure** a.k.a **Prefix tree**\n\nLet\'s understand **Trie first**,\n**Trie** is basically a **tree** that has some kind of **root node** & each node can have up to **26 children in this problem**. Because we have **lower case character from a to z**. So, basically each **node represent\'s a single character**. And each node could have up to 26 additional children:\n\n![image](https://assets.leetcode.com/users/images/f713156d-16ed-4f90-86f3-9e49c91cff9d_1643345343.9775767.png)\n\nAnd basically word in this example means, let\'s take **"a"** having child **"b" -> with "c"**, so that\'s will be a **single word**. And if we insert the word **"abc"** in our **trie**, so basically how\'s it looks like:\n\n![image](https://assets.leetcode.com/users/images/09de3579-2be4-43a2-8fba-4b6c1c268cf4_1643359099.5805793.png)\n\nOne additional thing we have to say is, for a particular node such as **"c"** this is the **end of the word**. Because if we **added another word** example:- **"ab"**. So, we don\'t add them back again as if you notice they are already available to us, we just **gonna re-use** these characters. So, we have 2 word\'s along this **path "abc" & "ab"**\nBasically, all words start with **"a"** are gonna be here, that\'s what it make it **efficient**. That\'s why it\'s called **prefix tree**.\n\n`Now, you have understood how Trie aka Prefix Tree work.`\n\nNow let\'s take an example & build our tree,\n**Input**\n```\n["WordDictionary","addWord","addWord","addWord","search","search","search","search"]\n[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]\n```\n**Output**\n```\n[null,null,null,null,false,true,true,true]\n```\n* The first word we add is **"bad". "b" -> "a" -> "d"**\n\n* Next we adding another word **"dad"**. So, we have to start with **different path**. As, these two word\'s have a **different prefix**. One start with **"b"** and one start with **"d"**. So, let\'s add it: **"d" -> "a" -> "d"**\n\n* We have one last word before we start searching, this one gonna be **"mad"**. So, we don\'t have **"m"**, then let\'s add it: **"m" -> "a" -> "d"**\n\n![image](https://assets.leetcode.com/users/images/dbb4b468-4cd3-4347-aa88-328c6ff70bee_1643341320.915674.gif)\n\nSo far we have **3 word\'s** and all of them end with different **"d"**. But they all **3 of them have different prefix** that\'s why they are along different path\'s.\n\n![image](https://assets.leetcode.com/users/images/e5e9489e-632b-4536-9596-4fddf1ddeb5c_1643341419.4522402.png)\n\n`Now let\'s go for searching path:-`\n\n* So, first word we gonna search for **"pad"**. We gonna **start** at **beginning**. First we gonna try are there any **"p"** in this. That means immediately we **return false** as **"pad"** doesn\'t exist in our input.\n\n* Now, we search another word **"bad"**. So, we **start at the root** and see there are any **"b"**. Yes, we have **"b"**. now we check does this **"b"** have a child **"a"**, yes it does. Now last character **"d"** does **"a"** has a child **"d"**, yes it does have. Lastly we have to say the last character **"d"** is in our **trie**, which designated as the end of the word. Sice it\'s **marked red**. Therefore, we **return true** for this input **"bad"**\n\n\n* Now, in this search we have **".ad"**, the dot **"."** character matches any character. So, we start at the root and go to any of the path and to do that we have to use **DFS or backtracking approach**. So, let\'s say first path we decided **"b"**. now we check does this **"b"** have a child **"a"**, yes it does. Now last character **"d"** does **"a"** has a child **"d"**, yes it does have. Lastly we have to say the last character **"d"** in our trie, is designated as the end of the word. Therefore, we **return true** for this input **".ad"**\n\n\n* One last search, In this we have **"b.."**. So, we start at the root and see there are any **"b"**. Yes, we have **"b"**. Now we check do we have any character to go below for our current dot **"."**, yes we have **"a"**. Now we are looking for any character for our last **dot "."** Yes we have **"d"** & it is end of the word. Therefore, we **return true** for this input **"b.."**\n\nNow understand this ***VISUALLY, it\'s not super hard.***\n\n![image](https://assets.leetcode.com/users/images/ddecc948-77d6-45d6-bcd3-83f7b9ace6ff_1643343393.560126.gif)\n\n\n**Now, let\'s code it up:**\n\n**Java**\n```\nclass WordDictionary {\n    private WordDictionary[] children;\n    boolean isEndOfWord;\n    // Initialize your data structure here. \n    public WordDictionary() {\n        children = new WordDictionary[26];\n        isEndOfWord = false;\n    }\n    \n    // Adds a word into the data structure. \n    public void addWord(String word) {\n        WordDictionary curr = this;\n        for(char c: word.toCharArray()){\n            if(curr.children[c - \'a\'] == null)\n                curr.children[c - \'a\'] = new WordDictionary();\n            curr = curr.children[c - \'a\'];\n        }\n        curr.isEndOfWord = true;\n    }\n    \n    // Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter. \n    public boolean search(String word) {\n        WordDictionary curr = this;\n        for(int i = 0; i < word.length(); ++i){\n            char c = word.charAt(i);\n            if(c == \'.\'){\n                for(WordDictionary ch: curr.children)\n                    if(ch != null && ch.search(word.substring(i+1))) return true;\n                return false;\n            }\n            if(curr.children[c - \'a\'] == null) return false;\n            curr = curr.children[c - \'a\'];\n        }\n        return curr != null && curr.isEndOfWord;\n    }\n}\n```\n**C++**\n```\nclass WordDictionary {\n    vector<WordDictionary*> children;\n    bool isEndOfWord;\npublic:\n    // Initialize your data structure here. \n    WordDictionary(): isEndOfWord(false){\n        children = vector<WordDictionary*>(26, nullptr);\n    }\n    \n    // Adds a word into the data structure. \n    void addWord(string word) {\n        WordDictionary *curr = this;\n        for(char c: word){\n            if(curr->children[c - \'a\'] == nullptr)\n                curr->children[c - \'a\'] = new WordDictionary();\n            curr = curr->children[c - \'a\'];\n        }\n        curr->isEndOfWord = true;\n    }\n    \n    // Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter. \n    bool search(string word) {\n        WordDictionary *curr = this;\n        for(int i = 0; i < word.length(); ++i){\n            char c = word[i];\n            if(c == \'.\'){\n                for(auto ch: curr->children)\n                    if(ch && ch->search(word.substr(i+1))) return true;\n                return false;\n            }\n            if(curr->children[c - \'a\'] == nullptr) return false;\n            curr = curr->children[c - \'a\'];\n        }\n        return curr && curr->isEndOfWord;\n    }\n};\n```\n**Python**\n```\nclass WordDictionary:\n\n    def __init__(self):\n        \n        # Initialize your data structure here.\n        self.children = [None]*26\n        self.isEndOfWord = False\n        \n\n    def addWord(self, word: str) -> None:\n\n        # Adds a word into the data structure.\n        curr = self\n        for c in word:\n            if curr.children[ord(c) - ord(\'a\')] == None:\n                curr.children[ord(c) - ord(\'a\')] = WordDictionary()\n            curr = curr.children[ord(c) - ord(\'a\')]\n        \n        curr.isEndOfWord = 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        curr = self\n        for i in range(len(word)):\n            c = word[i]\n            if c == \'.\':\n                for ch in curr.children:\n                    if ch != None and ch.search(word[i+1:]): return True\n                return False\n            \n            if curr.children[ord(c) - ord(\'a\')] == None: return False\n            curr = curr.children[ord(c) - ord(\'a\')]\n        \n        return curr != None and curr.isEndOfWord\n```\nANALYSIS :-\n* **Time Complexity :-** BigO(M) for well defined words, But in worse case BigO(M.26^N)\n\n* **Space Complexity :-** BigO(1) for well defined words, But for worst case BigO(M)
['C', 'Python', 'Java']