127. 单词接龙

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

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。

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

示例 1：

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

示例 2：

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

提示：

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

---

 

 

思路1：bfs

　　参考：https://www.cnblogs.com/qiu-yu/p/14929599.html

　　与参考链接思路相似，需要构造状态转换表，再次bfs

 

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, List<String>> map = new HashMap<>();
        wordList.add(beginWord);
        for (String word: wordList) {
            map.put(word, new ArrayList<>());
        }
        for (int i=0; i<wordList.size(); i++) {
            String k1 = wordList.get(i);
            for (int j=i+1; j<wordList.size(); j++) {
                String k2 = wordList.get(j);
                if (connect(k1, k2)) {
                    List<String> list1 = map.get(k1);
                    list1.add(k2);
                    map.put(k1, list1);
                    List<String> list2 = map.get(k2);
                    list2.add(k1);
                    map.put(k2, list2);
                }
            }
        }

        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        Set<String> seen = new HashSet<>();
        seen.add(beginWord);
        int step = 1;

        while (!q.isEmpty()) {
            step++;
            int size = q.size();
            for (int i=0; i<size; i++) {
                String status = q.poll();
                for (String nextStatus: map.get(status)) {
                    if (endWord.equals(nextStatus)) {
                        return step;
                    }
                    if (!seen.contains(nextStatus)) {
                        q.offer(nextStatus);
                        seen.add(nextStatus);
                    }
                }
            }
        }
        return 0;
    }

    private boolean connect(String word1, String word2) {
        int cnt = 0;
        for (int i=0; i<word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i))
                cnt++;
        }
        return cnt == 1;
    }
}