LeetCode：127. 单词接龙

问题链接

127. 单词接龙

问题描述

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 `wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

示例

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

解题思路

这道题我一开始直接广度优先搜索暴力解题，结果喜提“超出时间限制”......
我们可以对所有的单词的关联关系进行建图，然后再使用广度优先搜索（具体可以看题解）。

代码示例（JAVA）

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 0.如果endWord不在wordList中，直接结束
        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 1.建图
        Map<String, Integer> map = new HashMap<>();
        List<List<String>> list = new ArrayList<>();
        wordList.add(beginWord);
        for (String word : wordList) {
            drawPicture(map, list, word);
        }
        // 2.广度优先搜索求解
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        int res = 1;
        while (!queue.isEmpty()) {
            res++;
            int curSize = queue.size();
            for (int i = 1; i <= curSize; i++) {
                String str = queue.poll();
                int pos = map.get(str);
                for (String newStr : list.get(pos)) {
                    if (visited.add(newStr)) {
                        if (endWord.equals(newStr)) {
                            return res / 2 + 1;
                        }
                        queue.add(newStr);
                    }
                }
            }
        }
        return 0;
    }

    private void drawPicture(Map<String, Integer> map, List<List<String>> list, String word) {
        // 0.新增结点信息
        addNode(map, list, word);
        // 1.当前结点对应关系在list中的位置
        int pos = map.get(word);
        // 2.建立结点关联关系
        for (int i = 0; i < word.length(); i++) {
            StringBuilder newString = new StringBuilder(word);
            newString.setCharAt(i, '*');
            String newStr = newString.toString();
            addNode(map, list, newStr);
            int newStrPos = map.get(newStr);
            list.get(pos).add(newStr);
            list.get(newStrPos).add(word);
        }
    }

    private void addNode(Map<String, Integer> map, List<List<String>> list, String word) {
        // 0.有重复的，直接结束
        if (map.containsKey(word)) {
            return;
        }
        // 1.新建结点
        map.put(word, map.size());
        list.add(new ArrayList<>());
    }
}

执行结果