基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
示例 1：
代码语言：javascript复制输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1示例 2：
代码语言：javascript复制输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2示例 3：
代码语言：javascript复制输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3思路与算法
经过分析可知，题目要求将一个基因序列
变化至另一个基因序列
，需要满足一下条件：序列
与 序列
之间只有一个字符不同； 变化字符只能从
中进行选择； 变换后的序列
一定要在字符串数组
中。 已知方法一中广度优先搜索方法，我们可以对
进行预处理，只在合法的基因变化进行搜索即可。由于题目中给定的
基因库的长度较小，因此可以直接在对
进行预处理，找到基因库中的每个基因的合法变换，而不需要像方法一中每次都需要去计算基因的变化序列，我们将每个基因的合法变化关系存储在邻接表
中，每次基因变化搜索只在
中进行即可。
代码语言：javascript复制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;
}
};复杂度分析
时间复杂度：
，其中
为基因序列的长度，
为数组
的长度。计算合法的基因变化
需要的时间为
，广度优先搜索时，队列中最多有
个元素，需要的时间为
，因此时间复杂度为
。
空间复杂度：
，其中
为数组
的长度。计算合法的基因变化
需要的空间为
，队列中最多有
个元素，因此空间复杂度为
。
