题解 | #基因变异最小次数#
基因变异最小次数
https://www.nowcoder.com/practice/ca6b659a3fde42c59276c9db98febd94
知识点:map dfs
思路:变量cnt
改为mutations
表示突变的次数。size
变更为currentLevelSize
表示当前层的大小,poll
变为currentStr
表示当前处理的字符串。getDiff
方法改为isOneMutationAway
表示判断两个字符串是否仅相差一个突变即可
编程语言:java
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param start string字符串 * @param end string字符串 * @param bank string字符串一维数组 * @return int整型 */ public int minMutation(String start, String end, String[] bank) { int bankSize = bank.length; boolean[] visited = new boolean[bankSize]; Queue<String> queue = new ArrayDeque<>(); int mutations = -1; queue.offer(start); while (!queue.isEmpty()) { int currentLevelSize = queue.size(); mutations++; for (int i = 0; i < currentLevelSize; i++) { String currentStr = queue.poll(); if (end.equals(currentStr)) { return mutations; } for (int j = 0; j < bankSize; j++) { if (!visited[j] && isOneMutationAway(currentStr, bank[j])) { queue.offer(bank[j]); visited[j] = true; } } } } return -1; } private boolean isOneMutationAway(String str1, String str2) { int mutations = 0; int length = str1.length(); for (int i = 0; i < length; i++) { if (str1.charAt(i) != str2.charAt(i)) { mutations++; } } return mutations == 1; } }