
Q: A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.
Suppose we need to investigate a mutation from a gene string start to a gene string end where one mutation is defined as one single character changed in the gene string.
- For example, "AACCGGTT" --> "AACCGGTA" is one mutation.
There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.
Given the two gene strings start and end and the gene bank bank, return the minimum number of mutations needed to mutate from start to end. If there is no such a mutation, return -1.
Note that the starting point is assumed to be valid, so it might not be included in the bank.
A: BFS (Breadth-First Search)268Please respect copyright.PENANAyd5QWW5Rq4
// better than use DFS as it just need to find out the shortest path.
class Solution {268Please respect copyright.PENANA49BMuQN21Q
public int minMutation(String start, String end, String[] bank) {268Please respect copyright.PENANAIF9YyNX3XB
// Initialize a queue queue and a set seen. The queue will be used for BFS and the set will be used to prevent visiting a node more than once. Initially, the queue and set should hold start.268Please respect copyright.PENANA8MY2xN0Yvt
Queue<String> queue = new LinkedList<>();268Please respect copyright.PENANA7N348inrLl
Set<String> seen = new HashSet<>();268Please respect copyright.PENANAS5MSyBYIdd
queue.add(start);268Please respect copyright.PENANAKqEZL9a7t2
seen.add(start);268Please respect copyright.PENANAtESJm2k7AN
268Please respect copyright.PENANA5eD6XyHtf4
int steps = 0;268Please respect copyright.PENANAQxuyDCMxBW
268Please respect copyright.PENANA6csPdkwTxB
while (!queue.isEmpty()) {268Please respect copyright.PENANA2YFl5nqlzi
int nodesInQueue = queue.size();268Please respect copyright.PENANAvOea4doeFh
for (int j = 0; j < nodesInQueue; j++) {268Please respect copyright.PENANAXslZYJKYOc
String node = queue.remove();268Please respect copyright.PENANAsisw47hiuC
// Perform a BFS. At each node, if node == end, return the number of steps so far. Otherwise, iterate over all the neighbors. For each neighbor, if neighbor is not in seen and neighbor is in bank, add it to queue and seen.
if (node.equals(end)) {268Please respect copyright.PENANAb3edi66CCf
return steps;268Please respect copyright.PENANA5rjdA1FLv3
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {268Please respect copyright.PENANAbuEw7gcZSb
for (int i = 0; i < node.length(); i++) {268Please respect copyright.PENANAMD1xjkcn8h
String neighbor = node.substring(0, i) + c + node.substring(i + 1);268Please respect copyright.PENANA9hcFX1540t
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {268Please respect copyright.PENANAYbomT2s3JQ
queue.add(neighbor);268Please respect copyright.PENANA9DwiMslvbQ
seen.add(neighbor);268Please respect copyright.PENANAIu3U38FK5J
}268Please respect copyright.PENANAUBFjOcQsoP
}268Please respect copyright.PENANAnDMzoJIi6r
}268Please respect copyright.PENANAhJBRaYP6tT
}268Please respect copyright.PENANAiwp9UXFDVQ
268Please respect copyright.PENANAnzFKCtwqEF
steps++;268Please respect copyright.PENANA38nNx0pjMn
}268Please respect copyright.PENANAEj83ATF1DB
// If we finish the BFS and did not find end, return -1.268Please respect copyright.PENANA6ecQbL2IwV
return -1;268Please respect copyright.PENANAn7Kzdwqab1
}268Please respect copyright.PENANAazX6ZNvOQy
}