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)198Please respect copyright.ＰＥＮＡＮＡl0zjWYiC01
// better than use DFS as it just need to find out the shortest path.
class Solution {198Please respect copyright.ＰＥＮＡＮＡtezZLSwje7
public int minMutation(String start, String end, String[] bank) {198Please respect copyright.ＰＥＮＡＮＡsKVdzG3fsH
// 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.198Please respect copyright.ＰＥＮＡＮＡwnmqmgvbi9
Queue<String> queue = new LinkedList<>();198Please respect copyright.ＰＥＮＡＮＡd1jcXHA65N
Set<String> seen = new HashSet<>();198Please respect copyright.ＰＥＮＡＮＡzus3MU8Qpz
queue.add(start);198Please respect copyright.ＰＥＮＡＮＡkOFM8xlmU7
seen.add(start);198Please respect copyright.ＰＥＮＡＮＡ3YIEtk6fkC
198Please respect copyright.ＰＥＮＡＮＡT7lWps887C
int steps = 0;198Please respect copyright.ＰＥＮＡＮＡlaGLIKa3LE
198Please respect copyright.ＰＥＮＡＮＡN2VAa1nIFr
while (!queue.isEmpty()) {198Please respect copyright.ＰＥＮＡＮＡfiSbuuIpmE
int nodesInQueue = queue.size();198Please respect copyright.ＰＥＮＡＮＡrV178IwwWh
for (int j = 0; j < nodesInQueue; j++) {198Please respect copyright.ＰＥＮＡＮＡ39GhG9wsd5
String node = queue.remove();198Please respect copyright.ＰＥＮＡＮＡduYAeSlNYw
// 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)) {198Please respect copyright.ＰＥＮＡＮＡsvtZHJ2Okc
return steps;198Please respect copyright.ＰＥＮＡＮＡGmyQUa9uxj
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {198Please respect copyright.ＰＥＮＡＮＡhdUAsnO2s0
for (int i = 0; i < node.length(); i++) {198Please respect copyright.ＰＥＮＡＮＡPgihg3srk4
String neighbor = node.substring(0, i) + c + node.substring(i + 1);198Please respect copyright.ＰＥＮＡＮＡrXDpX5WzNN
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {198Please respect copyright.ＰＥＮＡＮＡBuzzX2ojhn
queue.add(neighbor);198Please respect copyright.ＰＥＮＡＮＡKLSh6GF5gF
seen.add(neighbor);198Please respect copyright.ＰＥＮＡＮＡiIGWyCKYi3
}198Please respect copyright.ＰＥＮＡＮＡgcgTOttLGb
}198Please respect copyright.ＰＥＮＡＮＡiiJxolfR02
}198Please respect copyright.ＰＥＮＡＮＡIUAfDRVHqR
}198Please respect copyright.ＰＥＮＡＮＡtZqTpCskl2
198Please respect copyright.ＰＥＮＡＮＡR0aswFuUG4
steps++;198Please respect copyright.ＰＥＮＡＮＡmjmCpAndZJ
}198Please respect copyright.ＰＥＮＡＮＡPMUJIoYiDS
// If we finish the BFS and did not find end, return -1.198Please respect copyright.ＰＥＮＡＮＡgLALJFSwa2
return -1;198Please respect copyright.ＰＥＮＡＮＡXckDORng1W
}198Please respect copyright.ＰＥＮＡＮＡphdTTLnjTx
}
然後按「加至主畫面」