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

题目考察的知识点是：

BFS、循环、遍历。

题目解答方法的文字分析：

本题可以使用BFS是一种图遍历算法，它从给定的起始节点开始，逐层地向外扩展搜索，直到找到目标节点或搜索完整个图。在这道题中，我们将基因序列看作是一个图，每个基因序列为图中的一个节点，两个基因序列之间如果只有一个字符不同，那么它们之间存在一条边。

本题解析所用的编程语言：

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) {
        // write code here
        int n = bank.length;
        boolean[] visited = new boolean[n];
        Queue<String> queue = new ArrayDeque<>();
        int cnt = -1;
        queue.offer(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            cnt++;
            for (int i = 0; i < size; i++) {
                String poll = queue.poll();
                if (end.equals(poll)) {
                    return cnt;
                }
                for (int j = 0; j < n; j++) {
                    if (!visited[j] && getDiff(poll, bank[j])) {
                        queue.offer(bank[j]);
                        visited[j] = true;
                    }
                }
            }
        }
        return -1;
    }

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