题目形容
这是 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.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$）。
代码：
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;
}
}- 工夫复杂度：令
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/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布