x
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)257Please respect copyright.ＰＥＮＡＮＡFhGWnfSF4e
// better than use DFS as it just need to find out the shortest path.
class Solution {257Please respect copyright.ＰＥＮＡＮＡoewBBsflnR
public int minMutation(String start, String end, String[] bank) {257Please respect copyright.ＰＥＮＡＮＡCYpymie7lf
// 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.257Please respect copyright.ＰＥＮＡＮＡJbH4iEacm0
Queue<String> queue = new LinkedList<>();257Please respect copyright.ＰＥＮＡＮＡqpHdTWOyAL
Set<String> seen = new HashSet<>();257Please respect copyright.ＰＥＮＡＮＡvojkOmpsT4
queue.add(start);257Please respect copyright.ＰＥＮＡＮＡRMNRtJEs6g
seen.add(start);257Please respect copyright.ＰＥＮＡＮＡwQgI8vbIyE
257Please respect copyright.ＰＥＮＡＮＡnywRRAbLZr
int steps = 0;257Please respect copyright.ＰＥＮＡＮＡILQ9fV7ir6
257Please respect copyright.ＰＥＮＡＮＡUXO2xAB6DJ
while (!queue.isEmpty()) {257Please respect copyright.ＰＥＮＡＮＡI7L5l5taxl
int nodesInQueue = queue.size();257Please respect copyright.ＰＥＮＡＮＡvil6yMwSLC
for (int j = 0; j < nodesInQueue; j++) {257Please respect copyright.ＰＥＮＡＮＡ8io5kIIXRZ
String node = queue.remove();257Please respect copyright.ＰＥＮＡＮＡQlEfM0ePnV
// 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)) {257Please respect copyright.ＰＥＮＡＮＡz9qgvsRgtk
return steps;257Please respect copyright.ＰＥＮＡＮＡOLte3PzPIS
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {257Please respect copyright.ＰＥＮＡＮＡT94pTPNVXb
for (int i = 0; i < node.length(); i++) {257Please respect copyright.ＰＥＮＡＮＡYyvO66tPMX
String neighbor = node.substring(0, i) + c + node.substring(i + 1);257Please respect copyright.ＰＥＮＡＮＡM6WCcuKsaH
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {257Please respect copyright.ＰＥＮＡＮＡLW5CXhNttM
queue.add(neighbor);257Please respect copyright.ＰＥＮＡＮＡlBzYES1fWD
seen.add(neighbor);257Please respect copyright.ＰＥＮＡＮＡ8ap2Zgwl7V
}257Please respect copyright.ＰＥＮＡＮＡfJJv4WBcwj
}257Please respect copyright.ＰＥＮＡＮＡT9Jv0otwfI
}257Please respect copyright.ＰＥＮＡＮＡuf4tZbhtUU
}257Please respect copyright.ＰＥＮＡＮＡmRlVQuRfyf
257Please respect copyright.ＰＥＮＡＮＡRGRJwt1FnV
steps++;257Please respect copyright.ＰＥＮＡＮＡuDpjeU1PpI
}257Please respect copyright.ＰＥＮＡＮＡ3TA7fWFo5N
// If we finish the BFS and did not find end, return -1.257Please respect copyright.ＰＥＮＡＮＡtSY7P4lk2O
return -1;257Please respect copyright.ＰＥＮＡＮＡbqsMUIvaBI
}257Please respect copyright.ＰＥＮＡＮＡyzRtEcVFQp
}
