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

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.add(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[] currChars = curr.toCharArray();
                for (int j = 0; j < currChars.length; j++) {
                    char orig_char = currChars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig_char) {
                            continue;
                        }

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

                        if (dict.contains(transformed) && !visited.contains(transformed)) {
                            q.add(transformed);
                            visited.add(transformed);
                        }
                    }
                    currChars[j] = orig_char; // 恢复原始状态
                }
            }
        }

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

编程语言是Java。

该题考察的知识点包括：

• 广度优先搜索：使用队列实现广度优先搜索，寻找最短路径或转换序列。
• 集合的使用：将单词列表转换为集合，以便快速查找单词是否在列表中。
• 字符串处理：在单词的不同位置尝试替换字符，形成新的单词，并进行查找和比较。

代码的简短文字解释：这段代码解决了一个问题，即找出从给定的起始通过逐步转换，到达目标所需的最短转换序列长度。通过使用广度优先搜索的方法，从起始单词开始，逐步尝试将其每个位置的字符替换为字母，生成新的可能的转换单词，并查找是否在单词列表中。如果找到了目标单词，则返回转换序列的长度；否则，继续尝试下一轮替换。最终，如果无法找到从起始单词到目标单词的转换序列，则返回0表示无法完成转换。