443.最小基因变化

发表于： 分类于：
字数： 1453 阅读：≈ 3分钟

🧬 443.最小基因变化

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

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

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

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

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

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

思路

基本思想

题目的要求需要从起始基因变化到终止基因，并且每一步变化的基因需要出现在基因库中，相当于从起点到终点，每一步都需要在一个集合中找一步走，并且下一步与当前步的基因序列只能查一个字符，这可以抽象成一个图的遍历问题，求起点到终点的最短路径问题，而求最短路径问题可以使用广度优先遍历，每次走一步，一旦找到终点就说明找到了最短路径

问题是如何进行遍历，针对基因的变化来说，从起点基因出发，变化不同的位置以及相同位置变化成不同元素都会形成下一步可能基因变化，也就是说一个基因变化一步之后，会形成多个基因，在所有的下一步基因中，针对每一个基因又会变化出很多下下一步的基因，这样一步一步的变化，当某一步变化之后变成了最终的基因，那么到达这一步的步长就是变化次数

转换成广度优先遍历就是先从起点出发，然后借鉴层次遍历的思想，每一层中都是同一步变化得到的基因，下一层是当前层变化一次所得到的所有基因，为了防止基因的重复并且防止基因变化过程中出现循环的问题，使用一个遍历数组记录已变化过的基因，这样就可以实现每次变化的都是新基因，只要结果基因在基因库中，就一定能变化得到

执行流程

  1. 初始化队列，将起点加入队列中
  2. 针对每一层的的每一个基因，将其取出，代表进入下一层的变化，此时步长+1
  3. 从基因库中找到所有未遍历并且只与当前基因相差一个位置的基因序列
  4. 判断找到的基因序列是不是结果序列，不是的话就将其加入队列中，并且标记为已访问
  5. 这样针对每一层的每一个基因都从基因库中找到只相差一个位置的未遍历基因
  6. 一层一层的扩散，最终可以找到目标基因并返回结果

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    //每一步的变化都需要位于基因库中，并且一次只能变换一个字符
    //每变换一次都可能是不同的位置，所以形成了不同的基因，但是都是变换一步的基因
    //所以可以用一个图来形容这个变换过程，然后进行广度优先遍历
    //在每一步中都将下一步可能变化的基因找出来，然后依次遍历
    public int minMutation(String startGene, String endGene, String[] bank) {
        if(startGene.matches("\\s*")||endGene.matches("\\s*")||bank.length==0)
            return -1;
        Queue<String> queue=new LinkedList<>();
        int[] visited=new int[bank.length];
        int res=0;
        queue.offer(startGene);
        while(queue.size()>0){
            ++res;
            //遍历当前步的所有基因，进行下一步的变换
            int size=queue.size();
            for(int i=0;i<size;++i){
                String temp=queue.poll();
                //针对每一个当前步的基因，都从基因库中找到其下一步将会变化的基因
                for(int j=0;j<bank.length;++j){
                    //没访问过的基因才会变化，防止出现循环
                    if(visited[j]==0){
                        int diff=0;
                        //统计出当前基因与基因库中的当前基因有几个位置的差距
                        for(int k=0;k<temp.length();++k){
                            if(temp.charAt(k)!=bank[j].charAt(k))
                                ++diff;
                        }
                        //只有一个位置的差距说明当前基因下一步可能变化到这个基因上
                        if(diff==1){
                            //下一步就是目标基因，直接返回变化次数
                            if(bank[j].equals(endGene))
                                return res;
                            //下一步不是目标基因，标记成已访问并加入队列中
                            visited[j]=1;
                            queue.offer(bank[j]);
                        }
                    }
                }
            }
        }
        //这里都没找到，返回-1
        return -1;
    }
}

总结

主要就是问题的转换，将基因的变化问题要转换到已有的图的最短路径问题上，然后将基因的变化抽象成节点的遍历，每次遍历一步，广度优先遍历就可以求的最短的变化路径