433. Minimum Genetic Mutation 最小基因变化

@TOC

# 题目描述

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 = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]



# 解题方法

# BFS

# 分享 BFS 模板：

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

BFS总共有两个模板：

# 模板一：

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


# 模板二：

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;
}
};


# 复杂度

• 时间复杂度：，其中 是 Bank 中的单词个数，是基因的长度。
• 空间复杂度：

# 总结

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

# 日期

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