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)187Please respect copyright.ＰＥＮＡＮＡ3PmEVbGDvG
// better than use DFS as it just need to find out the shortest path.
class Solution {187Please respect copyright.ＰＥＮＡＮＡPxKKNjYRy7
public int minMutation(String start, String end, String[] bank) {187Please respect copyright.ＰＥＮＡＮＡLPjFibZbas
// 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.187Please respect copyright.ＰＥＮＡＮＡR5bfYrQBeL
Queue<String> queue = new LinkedList<>();187Please respect copyright.ＰＥＮＡＮＡDWcFKyYp28
Set<String> seen = new HashSet<>();187Please respect copyright.ＰＥＮＡＮＡuOwtBtp2x8
queue.add(start);187Please respect copyright.ＰＥＮＡＮＡ1OuSkDBjed
seen.add(start);187Please respect copyright.ＰＥＮＡＮＡtxki0X4orj
187Please respect copyright.ＰＥＮＡＮＡ1D9Iwi6E3X
int steps = 0;187Please respect copyright.ＰＥＮＡＮＡTNdbvW7lyj
187Please respect copyright.ＰＥＮＡＮＡ0621xkVHpQ
while (!queue.isEmpty()) {187Please respect copyright.ＰＥＮＡＮＡ9lMMMOFlJ7
int nodesInQueue = queue.size();187Please respect copyright.ＰＥＮＡＮＡESioUmAPVK
for (int j = 0; j < nodesInQueue; j++) {187Please respect copyright.ＰＥＮＡＮＡ3xFJSfxsxL
String node = queue.remove();187Please respect copyright.ＰＥＮＡＮＡ7h5LS3BODv
// 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)) {187Please respect copyright.ＰＥＮＡＮＡvJ7zLNvJ11
return steps;187Please respect copyright.ＰＥＮＡＮＡ4fa4fgOIQN
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {187Please respect copyright.ＰＥＮＡＮＡVHojz3bMXs
for (int i = 0; i < node.length(); i++) {187Please respect copyright.ＰＥＮＡＮＡ9kEq1JiVqx
String neighbor = node.substring(0, i) + c + node.substring(i + 1);187Please respect copyright.ＰＥＮＡＮＡy7GFwi1Ock
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {187Please respect copyright.ＰＥＮＡＮＡ3w5W3UE2ux
queue.add(neighbor);187Please respect copyright.ＰＥＮＡＮＡUBA9w5M954
seen.add(neighbor);187Please respect copyright.ＰＥＮＡＮＡtshTKdk4N2
}187Please respect copyright.ＰＥＮＡＮＡe54Jc4anlc
}187Please respect copyright.ＰＥＮＡＮＡliytUMRypq
}187Please respect copyright.ＰＥＮＡＮＡoH2JO3OoZB
}187Please respect copyright.ＰＥＮＡＮＡqzFVTiBZd9
187Please respect copyright.ＰＥＮＡＮＡOBWjA3G86k
steps++;187Please respect copyright.ＰＥＮＡＮＡokRwcd8IPP
}187Please respect copyright.ＰＥＮＡＮＡQRs1MBhXik
// If we finish the BFS and did not find end, return -1.187Please respect copyright.ＰＥＮＡＮＡjAoxE37qAP
return -1;187Please respect copyright.ＰＥＮＡＮＡOgF2teaClN
}187Please respect copyright.ＰＥＮＡＮＡTlU6nHHzs6
}
