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)425Please respect copyright.ＰＥＮＡＮＡlfcsd9P76Y
// better than use DFS as it just need to find out the shortest path.
class Solution {425Please respect copyright.ＰＥＮＡＮＡzqLMrlcPlg
public int minMutation(String start, String end, String[] bank) {425Please respect copyright.ＰＥＮＡＮＡdIRtpnzx49
// 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.425Please respect copyright.ＰＥＮＡＮＡeI8Pglfk2d
Queue<String> queue = new LinkedList<>();425Please respect copyright.ＰＥＮＡＮＡLyj3H2fqz3
Set<String> seen = new HashSet<>();425Please respect copyright.ＰＥＮＡＮＡUFhVLme2Eq
queue.add(start);425Please respect copyright.ＰＥＮＡＮＡKgwdhBwKqr
seen.add(start);425Please respect copyright.ＰＥＮＡＮＡkremPdxDr9
425Please respect copyright.ＰＥＮＡＮＡIYpc6nLV1p
int steps = 0;425Please respect copyright.ＰＥＮＡＮＡyZ8fmK6Zii
425Please respect copyright.ＰＥＮＡＮＡ2ioOmWY1J0
while (!queue.isEmpty()) {425Please respect copyright.ＰＥＮＡＮＡVTQ7XCYEJp
int nodesInQueue = queue.size();425Please respect copyright.ＰＥＮＡＮＡG7RQzvFJ3r
for (int j = 0; j < nodesInQueue; j++) {425Please respect copyright.ＰＥＮＡＮＡtPG9AZb1iF
String node = queue.remove();425Please respect copyright.ＰＥＮＡＮＡVn7eNu4qrX
// 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)) {425Please respect copyright.ＰＥＮＡＮＡL7MDqLO9Sr
return steps;425Please respect copyright.ＰＥＮＡＮＡMD6jKUHxwD
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {425Please respect copyright.ＰＥＮＡＮＡ4gjh0bDBYX
for (int i = 0; i < node.length(); i++) {425Please respect copyright.ＰＥＮＡＮＡwZCzHYMRoa
String neighbor = node.substring(0, i) + c + node.substring(i + 1);425Please respect copyright.ＰＥＮＡＮＡLZmQElRoFI
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {425Please respect copyright.ＰＥＮＡＮＡI8qbfsmOEH
queue.add(neighbor);425Please respect copyright.ＰＥＮＡＮＡi3WuuOsx9q
seen.add(neighbor);425Please respect copyright.ＰＥＮＡＮＡc8JP9A5twV
}425Please respect copyright.ＰＥＮＡＮＡfJR3EBPdBh
}425Please respect copyright.ＰＥＮＡＮＡcZ6AQ4NHlC
}425Please respect copyright.ＰＥＮＡＮＡ1sBXdU6c2g
}425Please respect copyright.ＰＥＮＡＮＡ8NCaOf4dPI
425Please respect copyright.ＰＥＮＡＮＡnalY0xAtnN
steps++;425Please respect copyright.ＰＥＮＡＮＡmfOaOprfRO
}425Please respect copyright.ＰＥＮＡＮＡmcX7yoxLLb
// If we finish the BFS and did not find end, return -1.425Please respect copyright.ＰＥＮＡＮＡeN97fZvkgJ
return -1;425Please respect copyright.ＰＥＮＡＮＡtvEY86J6SS
}425Please respect copyright.ＰＥＮＡＮＡNaWvrz1uAg
}
and then Add to home screen.