关于后端:综合笔试题难度-35常规图论搜索问题的若干解法

题目形容

这是 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多平台公布