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:
- Starting point is assumed to be valid, so it might not be included in the bank.
- If multiple mutations are needed, all mutations during in the sequence must be valid.
- 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
这道题跟之前的 Word Ladder 完全是一道题啊，换个故事就直接来啊，越来不走心了啊。不过博主做的时候并没有想起来是之前一样的题，而是先按照脑海里第一个浮现出的思路做的，发现也通过OJ了。博主使用的一种BFS的搜索，先建立bank数组的距离场，这里距离就是两个字符串之间不同字符的个数。然后以start字符串为起点，向周围距离为1的点扩散，采用BFS搜索，每扩散一层，level自加1，当扩散到end字符串时，返回当前level即可。注意我们要把start字符串也加入bank中，而且此时我们也知道start的坐标位置，bank的最后一个位置，然后在建立距离场的时候，调用一个count子函数，用来统计输入的两个字符串之间不同字符的个数，注意dist[i][j]和dist[j][i]是相同，所以我们只用算一次就行了。然后我们进行BFS搜索，用一个visited集合来保存遍历过的字符串，注意检测距离的时候，dist[i][j]和dist[j][i]只要有一个是1，就可以了，参见代码如下：
解法一：
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
if (bank.empty()) return -;
bank.push_back(start);
int res = , n = bank.size();
queue<int> q{{n - }};
unordered_set<int> visited;
vector<vector<int>> dist(n, vector<int>(n, ));
for (int i = ; i < n; ++i) {
for (int j = i + ; j < n; ++j) {
dist[i][j] = count(bank[i], bank[j]);
}
}
while (!q.empty()) {
++res;
for (int i = q.size(); i > ; --i) {
int t = q.front(); q.pop();
visited.insert(t);
for (int j = ; j < n; ++j) {
if ((dist[t][j] != && dist[j][t] != ) || visited.count(j)) continue;
if (bank[j] == end) return res;
q.push(j);
}
}
}
return -;
}
int count(string word1, string word2) {
int cnt = , n = word1.size();
for (int i = ; i < n; ++i) {
if (word1[i] != word2[i]) ++cnt;
}
return cnt;
}
};
下面这种解法跟之前的那道 Word Ladder 是一样的，也是用的BFS搜索。跟上面的解法不同之处在于，对于遍历到的字符串，我们不再有距离场，而是对于每个字符，我们都尝试将其换为一个新的字符，每次只换一个，这样会得到一个新的字符串，如果这个字符串在bank中存在，说明这样变换是合法的，加入visited集合和queue中等待下一次遍历，记得在下次置换字符的时候要将之前的还原。我们在queue中取字符串出来遍历的时候，先检测其是否和end相等，相等的话返回level，参见代码如下：
解法二：
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
if (bank.empty()) return -;
vector<char> gens{'A','C','G','T'};
unordered_set<string> s{bank.begin(), bank.end()};
unordered_set<string> visited;
queue<string> q{{start}};
int level = ;
while (!q.empty()) {
for (int i = q.size(); i > ; --i) {
string t = q.front(); q.pop();
if (t == end) return level;
for (int j = ; j < t.size(); ++j) {
char old = t[j];
for (char c : gens) {
t[j] = c;
if (s.count(t) && !visited.count(t)) {
visited.insert(t);
q.push(t);
}
}
t[j] = old;
}
}
++level;
}
return -;
}
};
再来看一种递归的解法，跟 Permutations 中的解法一有些类似，是遍历bank中的字符串，跟当前的字符串cur相比较，调用isDiffOne()函数判断，若正好跟cur相差一个字符，并且之前没有访问过，那么先在visited数组中标记为true，然后调用递归函数，若返回的不为-1，则用其更新结果res，因为-1代表无法变换成cur。调用完递归后恢复状态，在visited数组中标记为false。循环结束后，看res的值，若还是n+1，表示无法更新，返回-1，否则返回res+1，因为这里的res是变换了一次后到达目标字符串的最小变化次数，所以要加上当前的这次变换。至于isDiffOne()函数就没啥难度了，就是一个一个的比较，不同就累加计数器cnt，参见代码如下：
解法三：
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
if (bank.empty()) return -;
vector<bool> visited(bank.size(), false);
return helper(start, end, bank, visited);
}
int helper(string cur, string end, vector<string>& bank, vector<bool>& visited) {
if (cur == end) return ;
int n = bank.size(), res = n + ;
for (int i = ; i < n; ++i) {
if (visited[i] || !isDiffOne(bank[i], cur)) continue;
visited[i] = true;
int t = helper(bank[i], end, bank, visited);
if (t != -) res = min(res, t);
visited[i] = false;
}
return res == n + ? - : res + ;
}
bool isDiffOne(string& s1, string& s2) {
int cnt = , n = s1.size();
for (int i = ; i < n; ++i) {
if (s1[i] != s2[i]) ++cnt;
if (cnt > ) break;
}
return cnt == ;
}
};
类似题目：
参考资料：
https://leetcode.com/problems/minimum-genetic-mutation/
https://leetcode.com/problems/minimum-genetic-mutation/discuss/91491/dfs-java
https://leetcode.com/problems/minimum-genetic-mutation/discuss/91484/java-solution-using-bfs