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

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) {
        // 如果起始基因和目的基因相同，直接返回0
        if (beginWord.equals(endWord)) {
            return 0;
        }
        //将基因库转变成哈希集合，方便查找
        Set<String> bankSet = new HashSet<>(Arrays.asList(wordList));
        //如果目标基因不在基因库中，直接返回-1
        if (!bankSet.contains(endWord)) {
            return -1;
        }
        //定义一个队列，用来存储当前层的基因序列
        Queue<String> queue = new LinkedList<>();
        //用来判断结点是否被访问
        Set<String> visited = new HashSet<>();
        //将起始基因加入队列
        queue.offer(beginWord);
        //定义一个变量，用来记录变化次数
        int count = 1;

        while (!queue.isEmpty()) {
            count++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                int amount = visited.size();
                for (String s : wordList) {
                    if (isDiff(s, str) && !visited.contains(s)) {
                        visited.add(s);
                        queue.offer(s);
                        if (s.equals(endWord)) {
                            return count;
                        }
                    }
                }
                if (visited.size() == amount) {
                    return 0;
                }
            }
        }
        return 0;
    }

    public boolean isDiff(String str1, String str2) {
        int total = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                total++;
            }
        }
        return total == 1;
    }
}

本题所考察的知识点是最短路径的求法，所用编程语言是java.

关于这题其实是求起点到终点的最短路径长度，我们要懂得此题如何转化为图结构，然后求起点到终点的最短路径