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)233Please respect copyright.ＰＥＮＡＮＡynD2fKbVaH
// better than use DFS as it just need to find out the shortest path.
class Solution {233Please respect copyright.ＰＥＮＡＮＡLSayhQ9e8S
public int minMutation(String start, String end, String[] bank) {233Please respect copyright.ＰＥＮＡＮＡCqDJFbOodi
// 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.233Please respect copyright.ＰＥＮＡＮＡ7xZ5GeYMfx
Queue<String> queue = new LinkedList<>();233Please respect copyright.ＰＥＮＡＮＡpcozrznrdX
Set<String> seen = new HashSet<>();233Please respect copyright.ＰＥＮＡＮＡTRue4ajbKQ
queue.add(start);233Please respect copyright.ＰＥＮＡＮＡUvs3teSGmM
seen.add(start);233Please respect copyright.ＰＥＮＡＮＡRcFl5QFrVt
233Please respect copyright.ＰＥＮＡＮＡAerosCYC6A
int steps = 0;233Please respect copyright.ＰＥＮＡＮＡRDwtkuUdIK
233Please respect copyright.ＰＥＮＡＮＡSxg84MQq50
while (!queue.isEmpty()) {233Please respect copyright.ＰＥＮＡＮＡGRZ2vJiPNV
int nodesInQueue = queue.size();233Please respect copyright.ＰＥＮＡＮＡAiqLa0ejD2
for (int j = 0; j < nodesInQueue; j++) {233Please respect copyright.ＰＥＮＡＮＡmF3A1nIJ85
String node = queue.remove();233Please respect copyright.ＰＥＮＡＮＡrufcoUBTLI
// 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)) {233Please respect copyright.ＰＥＮＡＮＡtOaS8Nzehy
return steps;233Please respect copyright.ＰＥＮＡＮＡ7F0Gicv2Zt
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {233Please respect copyright.ＰＥＮＡＮＡ6AytlFBLJS
for (int i = 0; i < node.length(); i++) {233Please respect copyright.ＰＥＮＡＮＡkB4TyEU8jO
String neighbor = node.substring(0, i) + c + node.substring(i + 1);233Please respect copyright.ＰＥＮＡＮＡVkq32stb44
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {233Please respect copyright.ＰＥＮＡＮＡaylHnuZUVF
queue.add(neighbor);233Please respect copyright.ＰＥＮＡＮＡRlZOlSc0qw
seen.add(neighbor);233Please respect copyright.ＰＥＮＡＮＡ4q5gYLw8xM
}233Please respect copyright.ＰＥＮＡＮＡCzKhkFmMKK
}233Please respect copyright.ＰＥＮＡＮＡ4F9RmkWccH
}233Please respect copyright.ＰＥＮＡＮＡHNFw4cZRet
}233Please respect copyright.ＰＥＮＡＮＡUWlBkOusIh
233Please respect copyright.ＰＥＮＡＮＡH8McH2zSao
steps++;233Please respect copyright.ＰＥＮＡＮＡYKQsC7jSzK
}233Please respect copyright.ＰＥＮＡＮＡqrfzsY7uOR
// If we finish the BFS and did not find end, return -1.233Please respect copyright.ＰＥＮＡＮＡvisQuofyPc
return -1;233Please respect copyright.ＰＥＮＡＮＡNAISuvu526
}233Please respect copyright.ＰＥＮＡＮＡEBasaOSY5o
}
