最小基因变化
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 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思路与算法
经过分析可知，题目要求将一个基因序列
A
变化至另一个基因序列
B
，需要满足一下条件：序列
A
与 序列
B
之间只有一个字符不同； 变化字符只能从
\texttt{`A', `C', `G', `T'}
中进行选择； 变换后的序列
B
一定要在字符串数组
\textit{bank}
中。 已知方法一中广度优先搜索方法，我们可以对
\textit{bank}
进行预处理，只在合法的基因变化进行搜索即可。由于题目中给定的
\textit{bank}
基因库的长度较小，因此可以直接在对
\textit{bank}
进行预处理，找到基因库中的每个基因的合法变换，而不需要像方法一中每次都需要去计算基因的变化序列，我们将每个基因的合法变化关系存储在邻接表
\textit{adj}
中，每次基因变化搜索只在
\textit{adj}
中进行即可。
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
int m = start.size();
int n = bank.size();
vector<vector<int>> adj(n);
int endIndex = -1;
for (int i = 0; i < n; i++) {
if (end == bank[i]) {
endIndex = i;
}
for (int j = i + 1; j < n; j++) {
int mutations = 0;
for (int k = 0; k < m; k++) {
if (bank[i][k] != bank[j][k]) {
mutations++;
}
if (mutations > 1) {
break;
}
}
if (mutations == 1) {
adj[i].emplace_back(j);
adj[j].emplace_back(i);
}
}
}
if (endIndex == -1) {
return -1;
}
queue<int> qu;
vector<bool> visited(n, false);
int step = 1;
for (int i = 0; i < n; i++) {
int mutations = 0;
for (int k = 0; k < m; k++) {
if (start[k] != bank[i][k]) {
mutations++;
}
if (mutations > 1) {
break;
}
}
if (mutations == 1) {
qu.emplace(i);
visited[i] = true;
}
}
while (!qu.empty()) {
int sz = qu.size();
for (int i = 0; i < sz; i++) {
int curr = qu.front();
qu.pop();
if (curr == endIndex) {
return step;
}
for (auto & next : adj[curr]) {
if (visited[next]) {
continue;
}
visited[next] = true;
qu.emplace(next);
}
}
step++;
}
return -1;
}
};复杂度分析
时间复杂度：
O(m \times n^2)
，其中
m
为基因序列的长度，
n
为数组
\textit{bank}
的长度。计算合法的基因变化
\textit{adj}
需要的时间为
O(m \times n^2)
，广度优先搜索时，队列中最多有
n
个元素，需要的时间为
O(n)
，因此时间复杂度为
O(m \times n^2)
。
空间复杂度：
O(n^2)
，其中
n
为数组
\textit{bank}
的长度。计算合法的基因变化
\textit{adj}
需要的空间为
O(n^2)
，队列中最多有
n
个元素，因此空间复杂度为
O(n^2)
。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-11-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
