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

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) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(wordList));
        if (!wordSet.contains(endWord)) {
            return 0;
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                char[] arr = word.toCharArray();
                for (int j = 0; j < arr.length; j++) {
                    char originalChar = arr[j];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (ch == originalChar) {
                            continue;
                        }
                        arr[j] = ch;
                        String newWord = new String(arr);
                        if (newWord.equals(endWord)) {
                            return level + 1;
                        }
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                    arr[j] = originalChar;
                }
            }
        }
        return 0;
    }
}

本题知识点分析：

1.哈希表去重

2.队列的出队和入队

3.数学模拟

4.数组遍历

本题解题思路分析：

1.将当前单词中的每个字符替换为从 'a' 到 'z' 的所有可能的小写字母。这生成一个新的单词 newWord，并将其与 endWord 进行比较。

2.如果相等，则表示当前的转换序列已经达到目标单词，并返回 level + 1 作为所需的最小转换次数。

3.如果 newWord 在 wordSet 中，就被添加到 queue 中，并且还会从 wordSet 中删除，以避免重复访问相同的单词。

本题使用编程语言: Java