基因序列可以表示为一条由 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
思路与算法
经过分析可知,题目要求将一个基因序列
变化至另一个基因序列
,需要满足一下条件:序列
与 序列
之间只有一个字符不同; 变化字符只能从
中进行选择; 变换后的序列
一定要在字符串数组
中。 已知方法一中广度优先搜索方法,我们可以对
进行预处理,只在合法的基因变化进行搜索即可。由于题目中给定的
基因库的长度较小,因此可以直接在对
进行预处理,找到基因库中的每个基因的合法变换,而不需要像方法一中每次都需要去计算基因的变化序列,我们将每个基因的合法变化关系存储在邻接表
中,每次基因变化搜索只在
中进行即可。
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;
}
};
复杂度分析
时间复杂度:
,其中
为基因序列的长度,
为数组
的长度。计算合法的基因变化
需要的时间为
,广度优先搜索时,队列中最多有
个元素,需要的时间为
,因此时间复杂度为
。
空间复杂度:
,其中
为数组
的长度。计算合法的基因变化
需要的空间为
,队列中最多有
个元素,因此空间复杂度为
。