class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
queue<string> toVisit;
unordered_set<string> dict(bank.begin(), bank.end());
int dist = 0;
if(!dict.count(end)) return -1;
toVisit.push(start);
dict.insert(start); dict.insert(end);
while(!toVisit.empty()) {
int n = toVisit.size();
for(int i=0; i<n; i++) {
string str = toVisit.front();
toVisit.pop();
if(str==end) return dist;
addWord(str, dict, toVisit);
}
dist++;
}
return -1;
}
void addWord(string word, unordered_set<string>& dict, queue<string>& toVisit) {
dict.erase(word);
for(int i=0; i<word.size(); i++) {
char tmp = word[i];
for(char c:string("ACGT")) {
word[i] = c;
if(dict.count(word)) {
toVisit.push(word);
dict.erase(word);
}
}
word[i] = tmp;
}
}
};
class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
def toNumber(gene):
table = {v : i for i, v in enumerate('ATGC')}
return sum([table[g] * 1 << (2 * i) for i, g in enumerate(gene)])
bank = set(map(toNumber, bank))
start = toNumber(start)
end = toNumber(end)
queue = [(start, 0)]
viset = set([start])
while queue:
gene, step = queue.pop(0)
if gene == end:
return step
for x in range(8):
for y in range(4):
next = gene ^ (y << (x * 2))
if next in bank and next not in viset:
viset.add(next)
queue.append((next, step + 1))
return -1