433. Minimum Genetic Mutation 最小基因变化

作者： 负雪明烛 id： fuxuemingzhu 个人博客： https://fuxuemingzhu.cn/ 关键词：LeetCode, 力扣，算法，题解，解析，答案，433，基因，变化，BFS，广度优先搜索

---

题目地址: https://leetcode.com/problems/minimum-genetic-mutation/description/

题目描述

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

1. Starting point is assumed to be valid, so it might not be included in the bank.
2. If multiple mutations are needed, all mutations during in the sequence must be valid.
3. You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

题目大意

给出了一个起始基因 start，一个结束基因 end。

问能不能通过变换，每次变化当前基因的一位，并且变化后的这个基因在基因库中的为有效基因，最后变换成为 end。如果可以的话，返回变换的最小次数。如果不可以的话，返回 -1.

以题目的示例 2 为例：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

变化的过程如下所示：

解题方法

BFS

基本和 127. Word Ladder 一模一样的，只不过把 26 个搜索换成了 4 个搜索，所以代码只用改变搜索的范围，以及最后的返回值就行了。

很显然这个问题是 BFS 的问题，同样是走迷宫问题的 4 个方向。

分享 BFS 模板：

BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。

BFS总共有两个模板：

模板一：

如果不需要确定当前遍历到了哪一层，BFS 模板如下。

while queue 不空：
    cur = queue.pop()
    if cur 有效且未被访问过：
        进行处理
    for 节点 in cur 的所有相邻节点：
        if 该节点有效：
            queue.push(该节点)

模板二：

如果要确定当前遍历到了哪一层，BFS 模板如下。 这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

level = 0
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        if cur 有效且未被访问过：
            进行处理
        for 节点 in cur的所有相邻节点：
            if 该节点有效：
                queue.push(该节点)
    }
    level ++;

上面两个是通用模板，在任何题目中都可以用，是要记住的！

本题做法

由于本题需要知道变换了多少次，因此需要确定当前遍历到哪一层，故本题中直接套用模板二。

代码总体思路：

• 利用队列保存有效的字符串
• 只要队列不空，就持续循环：
  • 记录当前队列的长度，对队列中该长度的字符串逐一遍历：
    • 如果搜索到 end，直接返回当前的步数 step
    • 否则，对当前字符串中的每个字符，都转变成 ACGT四个字符，看新形成的字符串是否遇到过
      • 如果没遇到过，就放入队列之中。
  • 步数 + 1

其中判断字符串是否遇到过，有两种方法：

• 使用 set 保存所有已经遇到过的字符串；
• 直接从 bank 中删除已经遇到过的字符串。

Python, C++ 代码如下：

class Solution(object):
    def minMutation(self, start, end, bank):
        """
        :type start: str
        :type end: str
        :type bank: List[str]
        :rtype: int
        """
        bfs = collections.deque()
        bfs.append((start, 0))
        bankset = set(bank)
        while bfs:
            gene, step = bfs.popleft()
            if gene == end:
                return step
            for i in range(len(gene)):
                for x in "ACGT":
                    newGene = gene[:i] + x + gene[i+1:]
                    if newGene in bank and newGene != gene:
                        bfs.append((newGene, step + 1))
                        bank.remove(newGene)
        return -1

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> bank_set(bank.begin(), bank.end());
        queue<string> que;
        que.push(start);
        unordered_set<string> visited;
        visited.insert(start);
        int step = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; ++i) {
                string cur = que.front(); que.pop();
                if (cur == end) {
                    return step;
                }
                for (char gene : "ACGT") {
                    for (int j = 0; j < cur.size(); ++j) {
                        string next = cur;
                        next[j] = gene;
                        if (bank_set.count(next) && !visited.count(next)) {
                            que.push(next);
                            visited.insert(next);
                        }
                    }
                }
            }
            step ++;
        }
        return -1;
    }
};

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> q;
        const int N = start.size();
        q.push(start);
        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int s = 0; s < size; s++) {
                auto cur = q.front(); q.pop();
                if (cur == end) {
                    return step;
                }
                for (int i = 0; i < N; i++) {
                    for (char n : {'A', 'C', 'G', 'T'}) {
                        string next = cur.substr(0, i) + n + cur.substr(i + 1);
                        if (next == cur) continue;
                        for (auto it = bank.begin(); it < bank.end(); ++it) {
                            if (*it == next) {
                                q.push(next);
                                bank.erase(it);
                                break;
                            }
                        }
                    }
                }
            }
            step += 1;
        }
        return -1;
    }
};

复杂度

• 时间复杂度：$O(N*L)$，其中 $N$是 Bank 中的单词个数，$L$是基因的长度。
• 空间复杂度：$O(N)$

总结

1. BFS 模板题，而且出现频率挺高的，记住我的模板就行。

日期

2018 年 9 月 29 日 —— 国庆9天长假第一天！ 2018 年 12 月 28 日 —— 即将元旦假期 2022 年 5 月 7 日 —— 重启算法题解日更！