⌘[ Java ] 3 Solutions | Observations | Trie | HashMap
Solution 1 : \n TC : \n\t  buildDict : O(n), where n is the number of words in the dictionary\n\t  search : O(n*k), where k is the length of word we are checkin
# Solution 1 : \n* TC : \n\t*  buildDict : `O(n) `, where `n` is the number of words in the dictionary\n\t*  search : `O(n*k)`, where `k` is the length of word we are checking\n    \n* SC : `O(n)`\n* Drawback : `Kills memory as the dictionary increases`\n```\nclass MagicDictionary {\n    \n    HashMap<Integer, HashSet<String>> map; \n\t// HashSet / Arraylist, doesn\'t make a diff bcz it is given in the question -> given a list of "different" words\n    public MagicDictionary() {\n        map = new HashMap<>();\n    }\n    \n    public void buildDict(String[] dictionary) {\n        for(String word : dictionary) {\n            if(!map.containsKey(word.length())) {\n                map.put(word.length(), new HashSet<String>());\n            }\n            map.get(word.length()).add(word);\n        }\n    }\n    \n    public boolean search(String searchWord) {\n        if(!map.containsKey(searchWord.length()))\n            return false;\n        \n        for(String words : map.get(searchWord.length())) {\n            int count = 0;\n            for(int i=0;i<searchWord.length();i++) {\n                count += words.charAt(i) == searchWord.charAt(i) ? 0 : 1;\n            }\n            if(count == 1) return true;\n        }\n        return false;\n    }\n}\n ```\n \n # Solution 2: \nThe given constraints is an intuition to use `Trie` data-structure.\nCode Observations : \n* `Search Operation` is not optimized as we are changing one char and searching for the complete word again.\n\nComplexity Analysis : \n* TC : `O(n*m) + O(k*26*k)`, where `k` is the length of word we are searching\n* SC : `O(n*m)`\n ```\n class Node {\n    HashMap<Character, Node> children;\n    boolean isEnd;\n    Node() {\n        this.children = new HashMap<>();\n        this.isEnd = false;\n    }\n}\nclass MagicDictionary {\n    \n    private Node root;\n    private int maxLength;\n    \n    public MagicDictionary() {\n        this.root = new Node();\n        this.maxLength = 0;\n    }\n    \n    public void buildDict(String[] dictionary) {\n        for(String word : dictionary) {\n            Node curr = this.root;\n            maxLength = Math.max(maxLength, word.length());\n            for(char ch : word.toCharArray()) {\n                if(curr.children.get(ch) == null) \n                    curr.children.put(ch, new Node());\n                curr = curr.children.get(ch);\n            }\n            curr.isEnd = true;\n        }\n    }\n    \n    public boolean search(String searchWord) {\n        if(maxLength < searchWord.length()) \n            return false;\n        \n        char[] W = searchWord.toCharArray();\n        int n = W.length;\n        Node curr = this.root;\n        for(int i=0;i<n;i++) {\n            char original = W[i];\n            for(char ch=\'a\';ch<=\'z\';ch++) {\n                if(ch != original) \n                {\n                    W[i] = ch;\n                    // curr char changed -> search complete string\n                    if(searchWord(W)) return true;\n                    W[i] = original;\n                }\n            }\n        }\n        return false;\n    }\n    \n    private boolean searchWord(char[] W) {        \n        Node curr = this.root;\n        for(int i=0;i<W.length;i++) {\n            if(curr.children.get(W[i]) == null) return false;\n            curr = curr.children.get(W[i]);\n        }\n        return curr.isEnd;\n    }\n}\n```\n\n# Solution 3 : \nThis approach is bit more optimized in `search(searchWord)` functionality.\n* Complexity of below solution would be better in average cases but in worst case, matches with the above solution.\n```\nclass Node {\n    HashMap<Character, Node> children;\n    boolean isEnd;\n    Node() {\n        this.children = new HashMap<>();\n        this.isEnd = false;\n    }\n}\nclass MagicDictionary {\n    \n    private Node root;\n    private int maxLength;\n    \n    public MagicDictionary() {\n        this.root = new Node();\n        this.maxLength = 0;\n    }\n    \n    public void buildDict(String[] dictionary) {\n        for(String word : dictionary) {\n            Node curr = this.root;\n            maxLength = Math.max(maxLength, word.length());\n            for(char ch : word.toCharArray()) {\n                if(curr.children.get(ch) == null) \n                    curr.children.put(ch, new Node());\n                curr = curr.children.get(ch);\n            }\n            curr.isEnd = true;\n        }\n    }\n    \n    public boolean search(String searchWord) {\n        if(maxLength < searchWord.length()) \n            return false;\n        \n        char[] W = searchWord.toCharArray();\n        int n = W.length;\n        Node curr = this.root;\n        for(int i=0;i<n;i++) {\n            char original = W[i];\n            for(char ch=\'a\';ch<=\'z\';ch++) {\n                if(curr.children.get(ch) == null) continue;\n                if(ch != original) \n                {\n                    W[i] = ch;\n                    // curr char changed -> search for string ahead\n                    if(searchWord(curr.children.get(W[i]), W, i+1)) return true;\n                    W[i] = original;\n                }\n            }\n\t\t\t// if we can not go ahead -> return false\n            if(curr.children.get(W[i]) == null) return false;\n            curr = curr.children.get(W[i]);\n        }\n        return false;\n    }\n    \n    private boolean searchWord(Node curr, char[] W, int index) {        \n        // Node curr = this.root;\n        for(int i=index;i<W.length;i++) {\n            if(curr.children.get(W[i]) == null) return false;\n            curr = curr.children.get(W[i]);\n        }\n        return curr.isEnd;\n    }\n}\n```
['Trie', 'Java']