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)293Please respect copyright.ＰＥＮＡＮＡgzNADFRaQl
// better than use DFS as it just need to find out the shortest path.
class Solution {293Please respect copyright.ＰＥＮＡＮＡuwf2u7dUAO
public int minMutation(String start, String end, String[] bank) {293Please respect copyright.ＰＥＮＡＮＡCLfKDi0H1L
// 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.293Please respect copyright.ＰＥＮＡＮＡQiQiuBjUz7
Queue<String> queue = new LinkedList<>();293Please respect copyright.ＰＥＮＡＮＡ8pr6tO6Clp
Set<String> seen = new HashSet<>();293Please respect copyright.ＰＥＮＡＮＡB20PThYDQL
queue.add(start);293Please respect copyright.ＰＥＮＡＮＡvmpHU7p448
seen.add(start);293Please respect copyright.ＰＥＮＡＮＡNeRQs4Rb4g
293Please respect copyright.ＰＥＮＡＮＡRM2quQTRp5
int steps = 0;293Please respect copyright.ＰＥＮＡＮＡNiPXl4wbGM
293Please respect copyright.ＰＥＮＡＮＡUdkFyyAMWp
while (!queue.isEmpty()) {293Please respect copyright.ＰＥＮＡＮＡICkNiI0hWU
int nodesInQueue = queue.size();293Please respect copyright.ＰＥＮＡＮＡzVN5DXMAcV
for (int j = 0; j < nodesInQueue; j++) {293Please respect copyright.ＰＥＮＡＮＡvEXX0G9jer
String node = queue.remove();293Please respect copyright.ＰＥＮＡＮＡkVQopxotQ9
// 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)) {293Please respect copyright.ＰＥＮＡＮＡH0i3dd55am
return steps;293Please respect copyright.ＰＥＮＡＮＡlegjqOPbHA
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {293Please respect copyright.ＰＥＮＡＮＡqE1SdtIQVp
for (int i = 0; i < node.length(); i++) {293Please respect copyright.ＰＥＮＡＮＡA5piYZdoJs
String neighbor = node.substring(0, i) + c + node.substring(i + 1);293Please respect copyright.ＰＥＮＡＮＡDH1uUMkKgF
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {293Please respect copyright.ＰＥＮＡＮＡC7Yx9rw0Hj
queue.add(neighbor);293Please respect copyright.ＰＥＮＡＮＡbgydH7WN7z
seen.add(neighbor);293Please respect copyright.ＰＥＮＡＮＡOnmlimSc3V
}293Please respect copyright.ＰＥＮＡＮＡ9F52UOJuEs
}293Please respect copyright.ＰＥＮＡＮＡOYepg1sT45
}293Please respect copyright.ＰＥＮＡＮＡyYShUD3PLw
}293Please respect copyright.ＰＥＮＡＮＡ0SXEQsG9iJ
293Please respect copyright.ＰＥＮＡＮＡ8DjfiOd2fY
steps++;293Please respect copyright.ＰＥＮＡＮＡ8KlnO9UWwc
}293Please respect copyright.ＰＥＮＡＮＡHDivQTX559
// If we finish the BFS and did not find end, return -1.293Please respect copyright.ＰＥＮＡＮＡmT7k25guOz
return -1;293Please respect copyright.ＰＥＮＡＮＡh9H1sghUS7
}293Please respect copyright.ＰＥＮＡＮＡDofWa2PloG
}
然後按「加至主畫面」