最小基因变化Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

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

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

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

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

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

提示：

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

# 思路

Deque

# 解法


class Solution {
    
    public int minMutation(String start, String end, String[] bank) {
        // 将bank转换成hashset，这样查询就是o1时间复杂度
        Set<String> banker = Arrays.stream(bank).collect(Collectors.toSet());  
        // 如果end不是有效基因，直接返回-1  
        if(!banker.contains(end)){
            return -1;
        }
        // 创建个队列，以便于bfs遍历
        Deque<String> queue = new ArrayDeque<>();
        // 记录访问过的基因
        Set<String> visited = new HashSet<>();
        // 将start放入队列
        queue.offer(start);
        visited.add(start);
        int res = 0;

        while(!queue.isEmpty()){
            int size = queue.size();
            res++;
            for(int num = 0; num < size; num++){
                String string = queue.poll();
                for(int i = 0; i < string.length(); i++){
                    StringBuilder str = new StringBuilder(string);
                    String[] change = new String[4];
                    change[0] = str.replace(i, i + 1, "A").toString();
                    change[1] = str.replace(i, i + 1, "C").toString();
                    change[2] = str.replace(i, i + 1, "G").toString();
                    change[3] = str.replace(i, i + 1, "T").toString();
                    for(int j = 0; j < 4; j++){
                        if(change[j].equals(end)){
                            return res;
                        }
                        if(banker.contains(change[j]) && !visited.contains(change[j])){
                            queue.offer(change[j]);
                            visited.add(change[j]);
                        }
                    }
                }
            }
        }
        return -1;
    }

}

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
46
47

# 总结

分析出几种情况，然后分别对各个情况实现