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)259Please respect copyright.ＰＥＮＡＮＡxPWuixiwb5
// better than use DFS as it just need to find out the shortest path.
class Solution {259Please respect copyright.ＰＥＮＡＮＡh9E5YhohDB
public int minMutation(String start, String end, String[] bank) {259Please respect copyright.ＰＥＮＡＮＡMglYz0bnV2
// 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.259Please respect copyright.ＰＥＮＡＮＡETneVReiGe
Queue<String> queue = new LinkedList<>();259Please respect copyright.ＰＥＮＡＮＡKGLL6WaQOI
Set<String> seen = new HashSet<>();259Please respect copyright.ＰＥＮＡＮＡSoWLEWFBup
queue.add(start);259Please respect copyright.ＰＥＮＡＮＡp8fOoFNmIJ
seen.add(start);259Please respect copyright.ＰＥＮＡＮＡZNNxroT3On
259Please respect copyright.ＰＥＮＡＮＡaYkK3F08Cf
int steps = 0;259Please respect copyright.ＰＥＮＡＮＡHlYgGD2SIL
259Please respect copyright.ＰＥＮＡＮＡsWnscpYNtc
while (!queue.isEmpty()) {259Please respect copyright.ＰＥＮＡＮＡ7DZ2zEDbn3
int nodesInQueue = queue.size();259Please respect copyright.ＰＥＮＡＮＡ9eoW3r11o0
for (int j = 0; j < nodesInQueue; j++) {259Please respect copyright.ＰＥＮＡＮＡapF4t14Vjf
String node = queue.remove();259Please respect copyright.ＰＥＮＡＮＡnaBZiChbAX
// 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)) {259Please respect copyright.ＰＥＮＡＮＡKLWe57HvEW
return steps;259Please respect copyright.ＰＥＮＡＮＡsVa5XH9J68
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {259Please respect copyright.ＰＥＮＡＮＡaeGsqhFx7P
for (int i = 0; i < node.length(); i++) {259Please respect copyright.ＰＥＮＡＮＡAdNKA50iUx
String neighbor = node.substring(0, i) + c + node.substring(i + 1);259Please respect copyright.ＰＥＮＡＮＡ9mh9JBnUHA
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {259Please respect copyright.ＰＥＮＡＮＡZOKtWBgfos
queue.add(neighbor);259Please respect copyright.ＰＥＮＡＮＡLNqaxjcixR
seen.add(neighbor);259Please respect copyright.ＰＥＮＡＮＡijWFiFBlav
}259Please respect copyright.ＰＥＮＡＮＡm7UjjGryOS
}259Please respect copyright.ＰＥＮＡＮＡMUaVxjmb13
}259Please respect copyright.ＰＥＮＡＮＡoEtFgN1IbR
}259Please respect copyright.ＰＥＮＡＮＡ4pAiGJhYrA
259Please respect copyright.ＰＥＮＡＮＡhSfdizXEPx
steps++;259Please respect copyright.ＰＥＮＡＮＡTe4ewQGoXi
}259Please respect copyright.ＰＥＮＡＮＡ2C2vioIh9F
// If we finish the BFS and did not find end, return -1.259Please respect copyright.ＰＥＮＡＮＡamvXCNUei7
return -1;259Please respect copyright.ＰＥＮＡＮＡESjPUcr1uq
}259Please respect copyright.ＰＥＮＡＮＡQNAFpaqfZE
}
