LC 433. 最小基因变化
题目描述
这是 LeetCode 上的 433. 最小基因变化 ，难度为 中等。
基因序列可以表示为一条由 $8$ 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 $-1$ 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
示例 1：1
2
3输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1
示例 2：1
2
3输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2
示例 3：1
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']组成
BFS
为了方便，我们令 $S = start$、 $T = end$，将每个基因序列视为「状态」。
容易想到使用 BFS 进行求解，并使用「哈希表」记录到达某个状态所消耗的步数（同时为了快速判断某个状态是否合法，我们使用 Set 结构对 $bank[i]$ 进行转存）。
起始将 S 加入队列，并更新到达 S 所使用的步数为 $0$，然后进行常规的 BFS 过程：每次取出队头元素，尝试替换当前状态的某一位，来得到新的状态（限定新状态必须合法，即必须出现在 Set 中），如果新状态合法并且没有在记录步数的哈希表中出现过，则将新状态入队并更新得到新状态所用步数，否则丢弃新状态。
重复上述过程直到找到 T（返回具体步数） 或者队列为空（返回 $-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
33class Solution {
static char[] items = new char[]{'A', 'C', 'G', 'T'};
public int minMutation(String S, String T, String[] bank) {
Set<String> set = new HashSet<>();
for (String s : bank) set.add(s);
Deque<String> d = new ArrayDeque<>();
Map<String, Integer> map = new HashMap<>();
d.addLast(S);
map.put(S, 0);
while (!d.isEmpty()) {
int size = d.size();
while (size-- > 0) {
String s = d.pollFirst();
char[] cs = s.toCharArray();
int step = map.get(s);
for (int i = 0; i < 8; i++) {
for (char c : items) {
if (cs[i] == c) continue;
char[] clone = cs.clone();
clone[i] = c;
String sub = String.valueOf(clone);
if (!set.contains(sub)) continue;
if (map.containsKey(sub)) continue;
if (sub.equals(T)) return step + 1;
map.put(sub, step + 1);
d.addLast(sub);
}
}
}
}
return -1;
}
}
- 时间复杂度：令 $n$ 为
bank的数组长度（合法状态数），将bank存入Set结构复杂度为 $O(n)$，每个状态经过一步操作最多拓展出 $C = 32$ 个新基因（共有 $8$ 个位置，每个位置有 $4$ 个选择），BFS过程复杂度为 $O(C \times n)$。整体复杂度为 $O(C \times n)$ - 空间复杂度：$O(n)$
双向 BFS
同理，我们可以使用「双向 BFS」进行求解。
双向 BFS 与常规 BFS 相比，能够有效解决「搜索空间爆炸」的问题：
对双向 BFS 不熟悉的同学可以看前置🧀：(题解) 127. 单词接龙。
代码：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
41class Solution {
static char[] items = new char[]{'A', 'C', 'G', 'T'};
Set<String> set = new HashSet<>();
public int minMutation(String S, String T, String[] bank) {
set.add(S);
for (String s : bank) set.add(s);
if (!set.contains(T)) return -1;
Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
d1.addLast(S); d2.addLast(T);
Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
m1.put(S, 0); m2.put(T, 0);
while (!d1.isEmpty() && !d2.isEmpty()) {
int t = -1;
if (d1.size() <= d2.size()) t = update(d1, m1, m2);
else t = update(d2, m2, m1);
if (t != -1) return t;
}
return -1;
}
int update(Deque<String> d, Map<String, Integer> cur, Map<String, Integer> other) {
int m = d.size();
while (m-- > 0) {
String s = d.pollFirst();
char[] cs = s.toCharArray();
int step = cur.get(s);
for (int i = 0; i < 8; i++) {
for (char c : items) {
if (cs[i] == c) continue;
char[] clone = cs.clone();
clone[i] = c;
String sub = String.valueOf(clone);
if (!set.contains(sub) || cur.containsKey(sub)) continue;
if (other.containsKey(sub)) return other.get(sub) + step + 1;
d.addLast(sub);
cur.put(sub, step + 1);
}
}
}
return -1;
}
}
- 时间复杂度：令 $n$ 为
bank的数组长度（合法状态数），将bank存入Set结构复杂度为 $O(n)$，每个状态经过一步操作最多拓展出 $C = 32$ 个新基因（共有 $8$ 个位置，每个位置有 $4$ 个选择），BFS过程复杂度为 $O(C \times n)$。整体复杂度为 $O(C \times n)$ - 空间复杂度：$O(n)$
AStar 算法
若不考虑 bank 的限制，对于一个特定状态而言，我们可以任意选择一位替换为 $4$ 类字符之一，因此对于任意状态 $x$ 而言，其与目标状态 $T$ 的「理论最小转换步数」为两者对应位置不同字符的数量，而由于存在 bank 限制，实际最小步数必然满足「大于等于」该理论最小转换步数。
基于此，我们可以计算当前状态到目标状态的「理论最小转换步数」作为启发式函数，进行启发式搜索。
具体的，我们使用优先队列（堆）维护所有的状态，每次优先「启发值 = 理论最小转换步数」的状态进行优先出队拓展。
对「AStar 算法」不了解的同学可以看前置 🧀：发挥 A* 算法最大价值的关键点。
代码：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
43class Solution {
class Node {
String s;
int val;
Node(String _s) {
s = _s;
for (int i = 0; i < 8; i++) {
if (s.charAt(i) != T.charAt(i)) val++;
}
}
}
static char[] items = new char[]{'A', 'C', 'G', 'T'};
String S, T;
public int minMutation(String start, String end, String[] bank) {
Set<String> set = new HashSet<>();
for (String s : bank) set.add(s);
S = start; T = end;
PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
Map<String, Integer> map = new HashMap<>();
q.add(new Node(S));
map.put(S, 0);
while (!q.isEmpty()) {
Node node = q.poll();
char[] cs = node.s.toCharArray();
int step = map.get(node.s);
for (int i = 0; i < 8; i++) {
for (char c : items) {
if (cs[i] == c) continue;
char[] clone = cs.clone();
clone[i] = c;
String sub = String.valueOf(clone);
if (!set.contains(sub)) continue;
if (sub.equals(T)) return step + 1;
if (!map.containsKey(sub) || map.get(sub) > step + 1) {
map.put(sub, step + 1);
q.add(new Node(sub));
}
}
}
}
return -1;
}
}
- 时间复杂度：启发式搜索分析时空复杂度意义不大
- 空间复杂度：启发式搜索分析时空复杂度意义不大
建图 + DFS
由 S 和 $bank[i]$ 组成合法点集，且点集中任意两点之间存在无向边的充要条件是：点 $u$ 和点 $v$ 所代表的字符中，仅有一个位置字符不同。
因此我们可以将所有的点存入 list 中，假设 list 长度为 $n$。同时为了方便，我们人为确保 S 出现在头部（点编号为 $1$），T 出现在尾部（点编号为 $n$）。
遍历 list 进行建图（对于两字符串中仅有一位置不同的点进行连边操作），然后跑一遍从 $1$ 到 $n$ 的 DFS。
由于图中可能有环或无解，因此必须「设定一个最大搜索深度」并增加「最优解剪枝」，确保搜索过程结束。
最大搜索深度的设定可以利用反证法：如果 S 能够到达 T，那么最优路径中必然不存在环（否则可以把环去掉，得到一条更短的路径），即最优路径所经过的点的数量必然不超过 $n$。
代码：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
48
49
50
51
52
53
54class Solution {
int N = 15, M = 15 * 15 * 2 + 50, idx = 0, loc = 1;
int[] he = new int[N], e = new int[M], ne = new int[M];
int n, ans;
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
void dfs(int u, int fa, int depth) {
if (depth >= ans) return ; // 最优解剪枝
if (u == n) {
ans = depth;
return ;
}
for (int i = he[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs(j, u, depth + 1);
}
}
public int minMutation(String S, String T, String[] bank) {
List<String> list = new ArrayList<>();
list.add(S);
boolean ok = false;
for (String s : bank) {
if (s.equals(S)) continue;
if (s.equals(T)) {
ok = true;
continue;
}
list.add(s);
}
if (!ok) return -1;
list.add(T);
n = list.size();
ans = n;
Arrays.fill(he, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
int cnt = 0;
for (int k = 0; k < 8 && cnt <= 1; k++) {
if (list.get(i).charAt(k) != list.get(j).charAt(k)) cnt++;
}
if (cnt == 1) {
add(i + 1, j + 1); add(j + 1, i + 1);
}
}
}
dfs(1, -1, 0);
return ans == n ? -1 : ans;
}
}
- 时间复杂度：令
bank的长度为 $n$（即点集的数量级为 $n$），预处理出list的复杂度为 $O(n)$；建图操作的复杂度为 $O(C \times n^2)$，其中 $C = 8$ 基因序列长度；DFS过程由于设定了最大搜索深度，复杂度为 $O(n^2)$。整体复杂度为 $O(C \times n^2)$ - 空间复杂度：最坏情况下为完全图，复杂度为 $O(n^2)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.433 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
