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)208Please respect copyright.ＰＥＮＡＮＡgjmda1J3Vc
// better than use DFS as it just need to find out the shortest path.
class Solution {208Please respect copyright.ＰＥＮＡＮＡXFXwjZ45pz
public int minMutation(String start, String end, String[] bank) {208Please respect copyright.ＰＥＮＡＮＡAuEXZnzMfN
// 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.208Please respect copyright.ＰＥＮＡＮＡTICzJ8QcOu
Queue<String> queue = new LinkedList<>();208Please respect copyright.ＰＥＮＡＮＡDqXNLTMdEY
Set<String> seen = new HashSet<>();208Please respect copyright.ＰＥＮＡＮＡtKKg3ahYTY
queue.add(start);208Please respect copyright.ＰＥＮＡＮＡC3pXcwvdFf
seen.add(start);208Please respect copyright.ＰＥＮＡＮＡTFOAPfkapY
208Please respect copyright.ＰＥＮＡＮＡDB5FiCvHp3
int steps = 0;208Please respect copyright.ＰＥＮＡＮＡrsJltl8WCJ
208Please respect copyright.ＰＥＮＡＮＡgYf4j4hmYp
while (!queue.isEmpty()) {208Please respect copyright.ＰＥＮＡＮＡxPUCeM4na3
int nodesInQueue = queue.size();208Please respect copyright.ＰＥＮＡＮＡdidCXYQ4EW
for (int j = 0; j < nodesInQueue; j++) {208Please respect copyright.ＰＥＮＡＮＡex88zZfJIA
String node = queue.remove();208Please respect copyright.ＰＥＮＡＮＡY4V0Ilx5YS
// 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)) {208Please respect copyright.ＰＥＮＡＮＡNyhxVK7M1Z
return steps;208Please respect copyright.ＰＥＮＡＮＡEBm41aRJ4C
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {208Please respect copyright.ＰＥＮＡＮＡSZ7PWsNAJV
for (int i = 0; i < node.length(); i++) {208Please respect copyright.ＰＥＮＡＮＡDpV25jatg0
String neighbor = node.substring(0, i) + c + node.substring(i + 1);208Please respect copyright.ＰＥＮＡＮＡY0zlrhOlf4
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {208Please respect copyright.ＰＥＮＡＮＡeD8sGhrZ6w
queue.add(neighbor);208Please respect copyright.ＰＥＮＡＮＡtEVgYEBpoP
seen.add(neighbor);208Please respect copyright.ＰＥＮＡＮＡyuuJI7vKj7
}208Please respect copyright.ＰＥＮＡＮＡOrnMTN1rpn
}208Please respect copyright.ＰＥＮＡＮＡescz2pJluu
}208Please respect copyright.ＰＥＮＡＮＡ95YLFfQrBd
}208Please respect copyright.ＰＥＮＡＮＡ4ROmHqxDdF
208Please respect copyright.ＰＥＮＡＮＡNNIOiIRK2j
steps++;208Please respect copyright.ＰＥＮＡＮＡwurPOZu4k8
}208Please respect copyright.ＰＥＮＡＮＡidbOLjKSXM
// If we finish the BFS and did not find end, return -1.208Please respect copyright.ＰＥＮＡＮＡwjW0ZDiAuK
return -1;208Please respect copyright.ＰＥＮＡＮＡOmcmrfzMuT
}208Please respect copyright.ＰＥＮＡＮＡtyj0c0gIaG
}
