LeetCode精讲——676. 实现一个魔法字典（难度：中等）

一、题目

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

实现 MagicDictionary 类：

[1] MagicDictionary() 初始化对象
[2] void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
[3] 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

三、解题思路

首先，在初始化字典中数据的时候，就将其整理为key=字符串长度，value=同一长度的字符串集合这样的结构，便于后续查找的时候，可以方便的获取到相同长度的字符串集合。具体实现如下图所示：

然后通过待查询字符串searchWord的长度来找到字典中的字符串集合，然后针对每个字符进行对比，只有当不相同的字符数等于1的时候，才返回True，否则为False。具体实现如下图所示：

四、代码实现

class MagicDictionary {
    private Map<Integer, List<String>> dictMap = new HashMap();

    public MagicDictionary() {
    }
    
    // 将dictionary整理为：key=字符串长度，value=同一长度的字符串集合
    public void buildDict(String[] dictionary) {
        for (String dict : dictionary) {
            if (dictMap.get(dict.length()) == null) {
                List<String> list = new ArrayList();
                list.add(dict);
                dictMap.put(dict.length(), list);
            } else {
                dictMap.get(dict.length()).add(dict);
            }
        }
    }
    
    public boolean search(String searchWord) {
        // 从dictMap中获取与searchWord相同长度的字符串集合——searchList
        List<String> searchList;
        if (dictMap.isEmpty() || (searchList = dictMap.get(searchWord.length())) == null) {
            return false;
        }

        // 针对searchList中每次字符串进行对比
        for (String dict : searchList) {
            int i = 0;
            int noMatchNums = 0;
            while (i < searchWord.length()) {
                if (searchWord.charAt(i) != dict.charAt(i)) {
                    noMatchNums++;
                }
                i++;
            }
            if (noMatchNums == 1) {
                return true;
            }
        }
        return false;
    }
}

今天的文章内容就这些了，最后一句话：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。

更多技术干活，欢迎大家关注公众号“爪哇缪斯”(^o^)/~ 「干货分享，每周更新」

题目来源：力扣