面试算法64：神奇的字典

题目

请实现有如下两个操作的神奇字典。

• 函数buildDict，输入单词数组用来创建一个字典。
• 函数search，输入一个单词，判断能否修改该单词中的一个字符，使修改之后的单词是字典中的一个单词。

例如，输入[“happy”，“new”，“year”]创建一个神奇字典。如果输入单词"now"进行查找操作，由于将其中的’o’修改成’e’就可以得到字典中的"new"，因此返回true。如果输入单词"new"，那么将其中的任意字符修改成另一个不同的字符都无法得到字典中的单词，因此返回false。

分析

可以将单词保存到前缀树中，然后在前缀树中查找只修改一个字符的字符串。
接下来着重讨论如何在前缀树中查找只修改一个字符的字符串。可以根据深度优先的顺序搜索前缀树的每条路径。如果到达的节点与字符串中的字符不匹配，则表示此时修改了字符串中的一个字符以匹配前缀树中的路径。如果到达对应字符串最后一个字符对应的节点时该节点的isWord字段的值为true，而且此时正好修改了字符串中的一个字符，那么就找到了修改字符串中一个字符对应的路径，符合题目的条件，可以返回true。

解

public class MagicDictionary {
    public static void main(String[] args) {
        String[] dict = {"happy","new","year"};
        MagicDictionary magicDictionary = new MagicDictionary();
        magicDictionary.buildDict(dict);
        System.out.println(magicDictionary.search("now"));
        System.out.println(magicDictionary.search("new"));
    }

    static class TrieNode {
        public TrieNode[] children;
        public boolean isWord;

        public TrieNode() {
            children = new TrieNode[26];
        }
    }

    TrieNode root;

    public MagicDictionary() {
        root = new TrieNode();
    }

    public void buildDict(String[] dict) {
        for (String word : dict) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                if (node.children[ch - 'a'] == null) {
                    node.children[ch - 'a'] = new TrieNode();
                }

                node = node.children[ch - 'a'];
            }

            node.isWord = true;
        }
    }

    public boolean search(String word) {
        return dfs(root, word, 0, 0);
    }

    private boolean dfs(TrieNode root, String word, int i, int edit) {
        if (root == null) {
            return false;
        }

        if (root.isWord && i == word.length() && edit == 1) {
            return true;
        }

        if (i < word.length() && edit <= 1) {
            boolean found = false;
            for (int j = 0; j < 26 && !found; j++) {
                int editt = j == word.charAt(i) - 'a' ? edit : edit + 1;
                found = dfs(root.children[j], word, i + 1, editt);
            }

            return found;
        }

        return false;
    }
}