题目

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

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 s_i 都在 wordList 中。注意， beginWord不需要在 wordList 中。
• s_k == 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 中的所有字符串 互不相同

题解

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Queue<String> queue = new ArrayDeque<>(Collections.singleton(beginWord));
    // 从开始单词开始 已经有一个序列了
    int result = 1, len = beginWord.length();
    // 两个单词是否能转换
    BiPredicate<String, String> canTransform = (s1, s2) -> {
        int diff = 0;
        for (int i = 0; i < len; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
                // 卫语句
                if (diff > 1) {
                    return false;
                }
            }
        }

        return diff == 1;
    };

    // bfs
    while (!queue.isEmpty()) {
        result++;
        int size = queue.size();
        // 遍历当前变换次数的所有单词
        while (size > 0) {
            String poll = queue.poll();
            Iterator<String> iterator = wordList.iterator();
            while (iterator.hasNext()) {
                String s = iterator.next();
                if (canTransform.test(poll, s)) {
                    if (s.equals(endWord)) {
                        return result;
                    }
                    // 下一次bfs遍历
                    queue.offer(s);
                    // 移除已使用的元素
                    iterator.remove();
                }
            }
            size--;
        }
    }

    return 0;
}