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

知识点：广度优先搜索

题目要求找到转换成目标字符串的单词个数，同时也包括了当前的初始单词，我们可以依次找出判断相差一个字符的单词，直至找到目标单词，这是一个非常典型的广度优先搜索问题。

由初始单词出发，每次遍历候选单词列表，每一层遍历去寻找相差一个字符的单词，加入队列中，每一层队列遍历时添加一个计数，以确定转换的次数，若队列为空，则说明没有有效的转换途径到达目标单词，返回0即可。

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
        int cnt = 0;
        int n = wordList.length;
        boolean[] visited = new boolean[n];
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(beginWord);
        while(!queue.isEmpty()) {
            cnt++;
            int size = queue.size();
            for(int k = 0; k < size; k++) {
                String poll = queue.poll();
                if(poll.equals(endWord)) {
                    return cnt;
                }
                for(int i = 0; i < n; i++) {
                    if(!visited[i] && getDiff(poll, wordList[i]) == 1) {
                        queue.offer(wordList[i]);
                        visited[i] = true;
                    }
                }
            }
        }
        return 0;
    }

    private int getDiff(String s1, String s2) {
        int n = s1.length();
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                cnt++;
            }
        }
        return cnt;
    }
}