# 433. Minimum Genetic Mutation

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

class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
if (bank.empty()) return -1;
bank.push_back(start);
int res = 0, n = bank.size();
queue<int> q{{n - 1}};
unordered_set<int> visited;
vector<vector<int>> dist(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
dist[i][j] = count(bank[i], bank[j]);
}
}
while (!q.empty()) {
++res;
for (int i = q.size(); i > 0; --i) {
int t = q.front(); q.pop();
visited.insert(t);
for (int j = 0; j < n; ++j) {
if ((dist[t][j] != 1 && dist[j][t] != 1) || visited.count(j)) continue;
if (bank[j] == end) return res;
q.push(j);
}
}
}
return -1;
}
int count(string word1, string word2) {
int cnt = 0, n = word1.size();
for (int i = 0; i < n; ++i) {
if (word1[i] != word2[i]) ++cnt;
}
return cnt;
}
};

class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
if (bank.empty()) return -1;
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 = 0;
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
string t = q.front(); q.pop();
if (t == end) return level;
for (int j = 0; 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 -1;
}
};

class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
if (bank.empty()) return -1;
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 0;
int n = bank.size(), res = n + 1;
for (int i = 0; i < n; ++i) {
if (visited[i] || !isDiffOne(bank[i], cur)) continue;
visited[i] = true;
int t = helper(bank[i], end, bank, visited);
if (t != -1) res = min(res, t);
visited[i] = false;
}
return res == n + 1 ? -1 : res + 1;
}
bool isDiffOne(string& s1, string& s2) {
int cnt = 0, n = s1.size();
for (int i = 0; i < n; ++i) {
if (s1[i] != s2[i]) ++cnt;
if (cnt > 1) break;
}
return cnt == 1;
}
};

Permutations

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

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation