433. 最小基因变化

看到美好，感受美好，屏蔽阴霾！

参考433. 最小基因变化 - 力扣（Leetcode）。

题目

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

• 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

输入：start = "AACCTTGG", end = "AATTCCGG", bank = ["AATTCCGG","AACCTGGG","AACCCCGG","AACCTACC"]
输出：-1
输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"]
输出：4
输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

解题思路

• 广度优先搜索+哈希表：考虑构造图,问题转化为start到end节点的最短路径,使用bfs初始化图同时扩展图的边;使用哈希表记录到达某个节点所需的变化次数。

广度优先搜索+哈希表

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        //判断endGene是否有效
        HashSet<String> set = new HashSet<>();
        for(String s : bank) set.add(s);
        if(!set.contains(endGene)) return -1;
        //构造图 并记录变化次数
        Deque<String> q = new ArrayDeque<>();
        HashMap<String,Integer> count = new HashMap<>();
        count.put(startGene,0);
        q.add(startGene);
        //bfs广度优先搜索
        while(q.size() > 0) {
            String gene = q.poll();
            if(gene.equals(endGene)) return count.get(gene);//能变化成功
            Iterator<String> it = set.iterator();
            while(it.hasNext()){
                String s = it.next();
                if(check(gene,s)){ //进行有效的变化
                    q.add(s);
                    count.put(s,count.get(gene) + 1);
                    it.remove();//除了删除 还可以用另一个哈希表记录是否搜索过
                }
            }
        }
        return -1;//不能变化成功
    }
    //start变化到有效的target是否只需要一步
    boolean check(String start,String target) {
        int count = 0;
        for(int i = 0; i < 8; i++){
            if(start.charAt(i) != target.charAt(i)) count += 1;
        }
        return count == 1;
    }
}

复杂度分析

• 时间复杂度：O(kn^2)，k为序列长度固定为8,n为bank数组长度,bfs搜索最多n次,每次用时不超过nk。
• 空间复杂度：O(n)，哈希表和队列所用空间都不超过n。