📌[ Java ] Simulation + Complete Explanation | Brute Force ➤ Optimised Solution
*\nPlease upvote if the explanation helps, as it keeps up the motivation to provide such posts.\n*Edit : Added code simulation at the end\n*\n\nExplanation Flow
****\nPlease upvote if the explanation helps, as it keeps up the motivation to provide such posts.\n**Edit : Added code simulation at the end**\n****\n\nExplanation Flow : \n* Given statements\n* Observations\n* Approach 1 - HashMap\n* Approach 2 - Trie\n* Modular Code\n* Complete Code\n\n\n**\u2714\uFE0F Given statements :**\n\n- Design a data structure that supports `adding new words` and `finding` if a string matches any previously added string.\n- `word` in addWord consists lower-case English letters.\n- `word` in search consist of  \'.\' or lower-case English letters\n\n**\u2714\uFE0FObservations :** \n\nThe only difficulty we will have is to handle `\'.\'` character.\n\nOne idea is to use a hashmap, where we map the `length of word -> List of word`. Following is the code for this approach :\n\n```\nclass WordDictionary {\n\n    private HashMap<Integer, Set<String>> map;\n\n    public WordDictionary() {\n        this.map = new HashMap<>();\n    }\n\n    public void addWord(String word) {\n\t\n        int l = word.length();\n        if (!this.map.containsKey(l)) {\n            this.map.put(l, new HashSet());\n        }\n        this.map.get(l).add(word);\n    }\n\t/* get list of words that have same length and match "word" with every word in the list*/\n    public boolean search(String word) {\n        int l = word.length();\n        if (this.map.containsKey(l)) {\n            for (String w : this.map.get(l)) {\n                int i = 0;\n                while ((i < l) && (w.charAt(i) == word.charAt(i) || word.charAt(i) == \'.\')) {\n                    i++;\n                }\n                if (i == l) return true;\n            }\n        }\n        return false;\n    }\n}\n```\n\n**\u2714\uFE0F Complexity Analysis:**\n* TC : `O(n * m)`, where `n` is the number of words and `m` is length of word we need to search.\n* SC : `O(n)`\n\n**\u2714\uFE0F Optimisation :** \n\nAn efficient data structure to use here would be `Trie` because\n* it provides better space optimisation as it stores common prefixes rather than complete words.\n( unlike hashmap )\n* Trie supports `search`, `insert` and delete operations in O(L) time where L is the length of the key.\n \n`Note :` The search space of Trie is much smaller than the Map based approach but still the worst case of both solutions are the same.\n\nI have broken down the code is modules : \n\n**TrieNode structure:**\n\n```\nclass Node {\n    HashMap<Character, Node> children;\n    boolean isEnd;\n    Node() {\n        this.children = new HashMap<>();\n        this.isEnd = false; // by default it is false\n    }\n}\n```\n****\n**addWord function :** \n\nIf you are familier with Trie this logic is same, if not, here is a one line explanation to it : \n\nAt each step, we need to check, if the child node to add is already present. If yes, go one step down else add it into the trie and then go one step down.\n[ Please refer this great article on Tries : https://leetcode.com/problems/implement-trie-prefix-tree/solution/ ]\n\n```\n\tpublic void addWord(String word) {\n\t\n        Node curr = this.root;\n        for(char ch : word.toCharArray()) {\n            if(!curr.children.containsKey(ch))\n                curr.children.put(ch, new Node());\n            curr = curr.children.get(ch);\n        }\n        curr.isEnd = true;\n    }\n```\n\n****\n**searchWord :**\n\nThere are two posibility for a character :\n1. ch == `\'.\'`\n2. `a` <= ch <= `z`\n\nIf `ch` is `.` then, we need to look for the word ahead, in the trie. For eg: If we are at `curr` in Trie and need to search for `.ab` then, we need to search for `ab` in all possible path of `curr` i.e. in `curr.children.keySet()`.  [ see simulation ]\n\nIf `ch` is a character[`a`, `z`]  then, it is a simple implementation to just check whether that `ch` exists or not.\n\n****\n**Simulation:**\nImages link ( If simulation speed is not aligned ) : https://drive.google.com/drive/folders/1INnKnTLryB4yaknIx04_WohE6XsYu2He?usp=sharing\n\n` `\n![image](https://assets.leetcode.com/users/images/a5278370-e5a0-4286-919f-46ce97858d6d_1643345130.5155442.gif)\n\n****\n\n```\npublic boolean search(String word) {\n        return search(word, this.root, 0);\n    }\n    \n    private boolean search(String word, Node curr, int index) {\n        \n        for(int i=index;i<word.length();i++) {\n            char ch = word.charAt(i);\n            if(ch == \'.\') {\n                // look for the word ahead\n                for(char c : curr.children.keySet()) {\n                    Node trieNode = curr.children.get(c);\n                    if(search(word, trieNode, i+1))\n                        return true;\n                }\n                return false;\n            } else {\n                if(!curr.children.containsKey(ch))\n                    return false;\n                curr = curr.children.get(ch);\n            }\n        }\n        return curr.isEnd;\n    }\n```\n\n****\n\n**\u2714\uFE0F Complete Code :** \n\n```\nclass Node {\n    HashMap<Character, Node> children;\n    boolean isEnd;\n    Node() {\n        this.children = new HashMap<>();\n        this.isEnd = false;\n    }\n}\n\nclass WordDictionary {\n\n    private Node root;\n    \n    public WordDictionary() {\n        this.root = new Node();\n    }\n    \n    public void addWord(String word) {\n        Node curr = this.root;\n        \n        for(char ch : word.toCharArray()) {\n            if(!curr.children.containsKey(ch))\n                curr.children.put(ch, new Node());\n            curr = curr.children.get(ch);\n        }\n        curr.isEnd = true;\n    }\n    \n    public boolean search(String word) {\n        return search(word, this.root, 0);\n    }\n    \n    private boolean search(String word, Node curr, int index) {\n        \n        for(int i=index;i<word.length();i++) {\n            char ch = word.charAt(i);\n            if(ch == \'.\') {\n                // look for the word ahead\n                for(char c : curr.children.keySet()) {\n                    Node trieNode = curr.children.get(c);\n                    if(search(word, trieNode, i+1))\n                        return true;\n                }\n                return false;\n            } else {\n                if(!curr.children.containsKey(ch))\n                    return false;\n                curr = curr.children.get(ch);\n            }\n        }\n        return curr.isEnd;\n    }\n}\n```\n\n**\u2714\uFE0F Complexity Analysis :** \n* TC : `O(\u2211 L)` + `O(26^X)`, where `L` is the length of words we are inserting in Trie, `X` is the length of word we are searching.\n* SC : `O(\u2211 L)`
['Trie', 'Java']