My Java Solution with Trie and Backtracking Search
Implement magic dictionary with two operations: buildDict and search. It\'s easy to come up with Trie to build a dict. The difficulty here for me is to implemen
Implement magic dictionary with two operations: `buildDict` and `search`. It\'s easy to come up with `Trie` to build a dict. The difficulty here for me is to implement the `search` operation.\nI use the backtracking way to find if there exists one word in the dict which has only one character different from the word I search.\n\nHere is the code. Hope it helps you think from a different way.\nI use a cnt to record the word\'s change times.\nThe key point is that if `cur.children[ch - \'a\']` is not null, we can search the next level without cnt + 1.\nOtherwise, we can search all other `cur.children` except the one that `cur.children[ch - \'a\']`.\nPlease point it out if anything is wrong.\n\n```\nclass MagicDictionary {\n\n    TrieNode root;\n    /** Initialize your data structure here. */\n    public MagicDictionary() {\n        root = new TrieNode();\n    }\n    \n    /** Build a dictionary through a list of words */\n    public void buildDict(String[] dict) {\n        for (String s : dict) {\n            TrieNode cur = root;\n            for (char ch : s.toCharArray()) {\n                if (cur.children[ch - \'a\'] == null) cur.children[ch - \'a\'] = new TrieNode();\n                cur = cur.children[ch - \'a\'];\n            }\n            cur.isWord = true;\n        }\n    }\n    \n    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */\n    public boolean search(String word) {\n        return search(root, word.toCharArray(), 0, 0);\n    }\n    \n    public boolean search(TrieNode cur, char[] word, int index, int cnt) {\n        if (cur == null || cnt > 1) {\n            return false;\n        }\n        if (index == word.length) {\n            return cur.isWord && cnt == 1;\n        }\n\n        for (int i = 0; i < 26; ++i) {\n            if (search(cur.children[i], word, index + 1, (word[index] - \'a\' != i) ? cnt + 1 : cnt)) {\n                return true;\n            }\n        }\n        return false;\n    }\n    \n    class TrieNode {\n        TrieNode[] children = new TrieNode[26];\n        boolean isWord = false;\n    }\n}
['Backtracking', 'Trie', 'Java']