【综合笔试题】难度 3/5，常规图论搜索问题的若干解法
题目描述
这是 LeetCode 上的 「433. 最小基因变化」 ，难度为 「中等」。
Tag : 「BFS」、「双向 BFS」、「图论 DFS」、「AStar 算法」、「启发式搜索」
基因序列可以表示为一条由 8个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库 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、end和bank[i]仅由字符['A', 'C', 'G', 'T']组成
BFS
为了方便，我们令 S = start、 T = end，将每个基因序列视为「状态」。
容易想到使用 BFS 进行求解，并使用「哈希表」记录到达某个状态所消耗的步数（同时为了快速判断某个状态是否合法，我们使用 Set 结构对 bank[i]进行转存）。
起始将 S 加入队列，并更新到达 S 所使用的步数为 0，然后进行常规的 BFS 过程：每次取出队头元素，尝试替换当前状态的某一位，来得到新的状态（限定新状态必须合法，即必须出现在 Set 中），如果新状态合法并且没有在记录步数的哈希表中出现过，则将新状态入队并更新得到新状态所用步数，否则丢弃新状态。
重复上述过程直到找到 T（返回具体步数） 或者队列为空（返回 --1）。
代码：
class 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. 单词接龙。
代码：
class 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* 算法最大价值的关键点。
代码：
class 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。
代码：
class 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;
}
}
最后
这是我们「刷穿 LeetCode」系列文章的第 No.433 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
相关文章
- 软件模块的几种复用形式研究
- 监控系统选型，一篇全搞定！
- 如何运用六西格玛培养有效的领导力？
- JVM实操篇-线上CPU占用飙升99%，系统响应延时飙升访问偶发白屏
- 广域铭岛上榜重庆两江新区软件和信息服务业企业能力清单
- Outlook 2019 for mac（电子邮件）v16.70 beta中文版
- 如何从丰田生产系统的原则中受益？
- 混合多云容灾， 云网架构保障业务永续
- vivo 实时计算平台建设实践
- TikTok正式进军游戏行业，网易成立大阪新工作室
- 蜗牛第4次冲刺上市，互联网百强公布
- 谷歌推出开源操作系统KataOS
- Visual Studio Code 1.73正式发布
- 振弦采集模块辅助功能寄存器之低功耗休眠
- 游戏企业从 Web2 切换到 Web3 的时候
- 云游戏三重门：体验、生态和硬件
- 2022 需求最大的 8 种编程语言
- 又一个国产开源崛起了！
- 性能测试（第3集）第22讲：JMeter其他技巧
- [SWPUCTF 2021 新生赛]Do_you_know_http解题思路