题解 | #牛群最短移动序列#
牛群最短移动序列
https://www.nowcoder.com/practice/6473462e05ac4665baec04caf628abdd
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.
关于这题其实是求起点到终点的最短路径长度,我们要懂得此题如何转化为图结构,然后求起点到终点的最短路径