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

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) {
        // 如果起始基因和目的基因相同，直接返回0
        if (start.equals(end)) {
            return 0;
        }
        //将基因库转变成哈希集合，方便查找
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        //如果目标基因不在基因库中，直接返回-1
        if (!bankSet.contains(end)) {
            return -1;
        }
        //定义一个队列，用来存储当前层的基因序列
        Queue<String> queue = new LinkedList<>();
        //将起始基因加入队列
        queue.offer(start);
        //定义一个变量，用来记录变化次数
        int count = 0;

        while (!queue.isEmpty()) {
            count++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                for (int j = 0; j < str.length(); j++) {
                    if (str.charAt(j) != end.charAt(j)) {
                        String mid = str.substring(0, j) + end.substring(j,
                                     j + 1) + str.substring(j + 1);
                        if (bankSet.contains(mid)) {
                            queue.offer(mid);
                        }
                        if (mid.equals(end)) {
                            return count;
                        }
                    }
                }
            }
        }
        return -1;
    }
}

本题考察的知识点是BFS求最短路径，所用编程语言是java.

我们可以将基因序列start看成源节点，end看作终端节点，基因库中的每个字符串看成一个结点，如果两个字符串不同的字符数只有一个，那么这两个基因序列有路径可达。我们的目标是找到一条从起点到终点的最短路径。对于示例1

输入：

"AAAAAAAA","CCCCCCCC",["AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAAACA","AAAAACCC","AAAACCCC","AAACCCCC","AACCCCCC","ACCCCCCC","CCCCCCCC"]

构成的图如下所示：

题目答案则是起点到终点的最短路径