Java implementation using Trie
The basic idea is:\n\nFirst, insert the dictionary list into the Trie;\n\nSecond, for each given word, scan character by character. For each character, try modi
The basic idea is:\n\nFirst, insert the dictionary list into the Trie;\n\nSecond, for each given word, scan character by character. For each character, try modify it and then call the search method in Trie. If trie.search() returns true then return true. If not then see if the Trie has exactly this character, if yes then keep going, if not return false.\n\nFinally, if reaches the end of the word return false. This means the dictionary has exactly this word. But modifying any of the character cannot fit in the dictionary.\n\nHere is my Java solution using Trie:\n```\nclass MagicDictionary {\n    private Trie trie;\n    \n    /** Initialize your data structure here. */\n    public MagicDictionary() {\n        trie = new Trie();\n    }\n    \n    /** Build a dictionary through a list of words */\n    public void buildDict(String[] dict) {\n        for(String word : dict) {\n            trie.insert(word);\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        TrieNode curr = trie.root;\n        int k = 0;\n        while(curr != null) {\n            if(k == word.length()) {\n                //System.out.println(1);\n                return false;\n            }\n            char c = word.charAt(k);\n            int index = c - 'a';\n            for(int i = 0; i < 26; i++) {\n                if(i == index)  continue;\n                if(curr.children[i] != null && searchHelper(word, k+1, curr.children[i])) {\n                    return true;\n                }\n            }\n            k++;\n            curr = curr.children[index];\n        }\n        return false;\n    }\n    \n    public boolean searchHelper(String word, int k, TrieNode node) {\n        if(k == word.length())  return node.isWord;\n        char c = word.charAt(k);\n        int index = c - 'a';\n        if(node.children[index] == null)    return false;\n        return searchHelper(word, k + 1, node.children[index]);\n    }\n}\n```\nThe Trie implementation is here:\n```\nclass TrieNode {\n    public char val;\n    public TrieNode[] children = new TrieNode[26];\n    public boolean isWord;\n    public TrieNode() {};\n    public TrieNode(char c) {\n        this.val = c;\n    }\n}\n\nclass Trie {\n    public TrieNode root;\n    public Trie() {\n        this.root = new TrieNode(' ');\n    }\n    public void insert(String word) {\n        TrieNode curr = root;\n        for(int i = 0; i < word.length(); i++) {\n            char c = word.charAt(i);\n            int index = c - 'a';\n            if(curr.children[index] == null) {\n                curr.children[index] = new TrieNode(c);\n            }\n            curr = curr.children[index];\n        }\n        curr.isWord = true;\n        return;\n    }\n}\n```
[]