题解 | #基因变异最小次数#

知识点：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;
    }
}