Java 题解 | #牛群最短移动序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param beginWord string字符串
     * @param endWord string字符串
     * @param wordList string字符串一维数组
     * @return int整型
     */
    public int ladderLength (String beginWord, String endWord, String[] wordList) {
        // write code here
        Set<String> dict = new HashSet<>(Arrays.asList(
                                             wordList)); // 将wordList转换为set，用于快速查找
        if (!dict.contains(endWord)) {
            return 0; // endWord不在字典中，无法到达
        }

        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        Set<String> visited = new HashSet<>(); // 记录已经访问过的节点
        visited.add(beginWord);

        int steps = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            steps++;

            for (int i = 0; i < size; i++) {
                String curr = q.poll();

                // 将当前节点的每个字母逐个替换为'a'~'z'，并查找是否有这个新的编号
                char[] chars = curr.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char origChar = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == origChar) {
                            continue;
                        }

                        chars[j] = c;
                        String newWord = new String(chars);
                        if (newWord.equals(endWord)) {
                            return steps + 1; // 找到了endWord，返回路径长度
                        }

                        if (dict.contains(newWord) && !visited.contains(newWord)) {
                            q.offer(newWord);
                            visited.add(newWord);
                        }
                    }
                    chars[j] = origChar; // 恢复原始状态
                }
            }
        }

        return 0; // 没有找到最短路径
    }
}

编程语言是Java。

这个题目考察的是图的广度优先搜索（BFS）算法。

首先将 wordList 转换为一个集合 dict，这样可以快速判断一个单词是否在 wordList 中。然后创建一个队列 q，将起始单词 beginWord 加入队列。使用一个集合 visited 记录已经访问过的单词，将起始单词加入 visited 中。

接下来就是典型的 BFS 算法。每次从队列中取出一个单词，并尝试将其每个字母逐个替换为 'a' 到 'z'，生成新的可能单词。如果新单词等于目标单词 endWord，则返回当前步数加1。否则，如果新单词在 dict 中且未被访问过，则将新单词加入队列 q 中，并将其加入 visited 集合中表示已经访问过。