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 = “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 中的所有字符串 互不相同

思路

随机到 一道题 和这道题一样，有些生疏了，来复习一下。

只相差一个字母的单词之间可以连接一条边，我们可以将这个问题看做无向图求最短路径。

一个难点是如何求一个单词的邻接单词，如果对于每个单词都遍历一次，然后一个一个字母比对，那么时间复杂度是，其中为单词长度，为大小，这样总的时间复杂是，会超时。

那么如何优化呢，一个突破口是单词全部由小写字母组成，那么我们枚举每个单词可能的邻接单词，一共有种可能，然后使用一个以#card=math&code=O%281%29&id=Ixz8I)时间查询是否在就好了，这样时间复杂度就降下来了，总的时间是。

代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int step = 1;
        Set<String> set = new HashSet<>(wordList);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Queue<String> q = new ArrayDeque<>();
        q.offer(beginWord);
        int n = beginWord.length();
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String str = q.poll();
                if (str.equals(endWord)) {
                    return step;
                }
                char[] arr = str.toCharArray();
                for (int j = 0; j < n; j++) {
                    char c = arr[j];
                    for (int k = 0; k < 26; k++) {
                        if (arr[j] == 'a' + k) {
                            continue;
                        }
                        arr[j] = (char) ('a' + k);
                        String s = new String(arr);
                        if (set.contains(s) && !visited.contains(s)) {
                            visited.add(s);
                            q.offer(s);
                        }
                    }
                    arr[j] = c;
                }
            }
            step++;
        }
        return 0;
    }
}