友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
433. 最小基因变化
基因序列可以表示为一条由 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']组成
思路分析
广度优先遍历，与 127. Word Ladder 解题思路是一样的。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-18 21:17:14
*/
public int minMutation(String startGene, String endGene, String[] bank) {
Set<String> banks = Arrays.stream(bank).collect(Collectors.toSet());
Set<String> used = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(startGene);
used.add(startGene);
int step = 0;
char[] chars = new char[]{'A', 'C', 'G', 'T'};
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curr = queue.poll();
if (curr.equals(endGene)) {
return step;
}
for (char c : chars) {
for (int j = 0; j < curr.length(); j++) {
if (c == curr.charAt(j)) {
continue;
}
StringBuilder sb = new StringBuilder(curr);
sb.setCharAt(j, c);
String ns = sb.toString();
if (banks.contains(ns) && !used.contains(ns)) {
queue.offer(ns);
used.add(ns);
}
}
}
}
step++;
}
return -1;
}