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

知识点：广度优先搜索

由一个字符串开始，寻找列表中只差一个字符的字符串，每次找到符合条件的字符串后，将其入队，出队时判断是否为目标字符串，每次遍历队列中的元素时，计数加一，出队时将相差一个字符的字符串继续入队，并将其标记，防止重复入队，当队列为空时，表示无目标字符串，返回-1。

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;
    }
}