LeetCode676.实现一个魔法字典

1.题目描述

• 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：
MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
 
示例：
输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False
 
提示：
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串 互不相同
1 <= searchWord.length <= 100
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 100 次 search

2.解题思路:

• 字典树实现

    static class MagicDictionary {

        TrieNode root;

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

        public void buildDict(String[] dictionary) {
            for (String str : dictionary) {
                buildDict(str);
            }
        }

        private void buildDict(String str) {
            TrieNode node = root;   //每个单词，都是从根节点开始遍历
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (node.children[ch - 'a'] == null) {
                    node.children[ch - 'a'] = new TrieNode();
                }
                node = node.children[ch - 'a'];
            }
            node.isEnd = true;
            node.setEnd(str);
        }

        /**
         * 1.理解题意
         * -输入一个单词，在字典树中是否符合该字符串的单词，要求其中有一个字符不相等
         * 2。解题思路
         * -从字典树根节点开始，并开始遍历字符串，当遇到不一样的单个字符时，从下一个节点位置开始遍历，单词后面的字符串是否相同
         */
        public boolean search(String searchWord) {
            TrieNode node = root;
            for (int i = 0; i < searchWord.length(); i++) {
                char ch = searchWord.charAt(i);
                for (int j = 0; j < 26; j++) {
                    //如果遇到相等的字符，或者不存在该节点 -->继续判断下一个节点
                    if (ch == (char) (j + 'a') || node.children[j] == null) {
                        continue;
                    }

                    //存在，且不想等，判断下一个节点和后面的字符串是否相等
                    if (searchPost(searchWord, i + 1, node.children[j])) {
                        return true;
                    }
                }
                if (node.children[ch - 'a'] == null) {
                    return false;
                }
                node = node.children[ch - 'a'];
            }
            return false;
        }

        private boolean searchPost(String searchWord, int index, TrieNode root) {
            TrieNode node = root;
            for (int i = index; i < searchWord.length(); i++) {
                char ch = searchWord.charAt(i);
                if (node.children[ch - 'a'] == null) {
                    return false;
                }
                node = node.children[ch - 'a'];
            }
            return node.isEnd;
        }
    }

• 字典树节点TrieNode

public class TrieNode {

    private static final int SIZE = 26;
    public boolean isEnd;
    public TrieNode[] children;
    //到该节点时的字符串是什么
    public String word;

    public TrieNode() {
        isEnd = false;
        children = new TrieNode[SIZE];
        word = "";
    }

    public void setEnd(String newWord) {
        isEnd = true;
        word = newWord;
    }
}

3.总结

• 字典树的创建与搜索