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

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) {
        if (start.equals(end)) {
            return 0;
        }
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        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;
    }
}

本题知识点分析：

1.哈希表的去重

2.队列的出队和入队

3.数学模拟

本题解题思路分析：

1.如果起始基因和结果已经相同，直接返回0

2.哈希表进行去重

3.如果目标基因不在基因库，直接返回-1

4.利用队列进行字符比较和包含比较

5.最终返回count的次数

本题使用编程语言: Java