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)291Please respect copyright.ＰＥＮＡＮＡhw3rmHmyAd
// better than use DFS as it just need to find out the shortest path.
class Solution {291Please respect copyright.ＰＥＮＡＮＡ3J21fibJnj
public int minMutation(String start, String end, String[] bank) {291Please respect copyright.ＰＥＮＡＮＡtk2IEjeV3L
// 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.291Please respect copyright.ＰＥＮＡＮＡJ0VLuMLBRn
Queue<String> queue = new LinkedList<>();291Please respect copyright.ＰＥＮＡＮＡvC84sSjORH
Set<String> seen = new HashSet<>();291Please respect copyright.ＰＥＮＡＮＡrOomjP3Z0n
queue.add(start);291Please respect copyright.ＰＥＮＡＮＡ4JYolQe5aF
seen.add(start);291Please respect copyright.ＰＥＮＡＮＡq92OShuFix
291Please respect copyright.ＰＥＮＡＮＡhbWNEnSWYy
int steps = 0;291Please respect copyright.ＰＥＮＡＮＡq0xqcNHrPH
291Please respect copyright.ＰＥＮＡＮＡL5Vp4fI6dX
while (!queue.isEmpty()) {291Please respect copyright.ＰＥＮＡＮＡgv4WlHoPeJ
int nodesInQueue = queue.size();291Please respect copyright.ＰＥＮＡＮＡXiC1nlaZ1J
for (int j = 0; j < nodesInQueue; j++) {291Please respect copyright.ＰＥＮＡＮＡ3YBJZaw3JD
String node = queue.remove();291Please respect copyright.ＰＥＮＡＮＡCYK6zihkSt
// 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)) {291Please respect copyright.ＰＥＮＡＮＡoxfuWx58Ni
return steps;291Please respect copyright.ＰＥＮＡＮＡ4UomdXMppn
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {291Please respect copyright.ＰＥＮＡＮＡmuX1ieHfnd
for (int i = 0; i < node.length(); i++) {291Please respect copyright.ＰＥＮＡＮＡFeJ0L6xOoU
String neighbor = node.substring(0, i) + c + node.substring(i + 1);291Please respect copyright.ＰＥＮＡＮＡDQSCQ4o3to
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {291Please respect copyright.ＰＥＮＡＮＡk1nn69sO43
queue.add(neighbor);291Please respect copyright.ＰＥＮＡＮＡIpzWAMUsSO
seen.add(neighbor);291Please respect copyright.ＰＥＮＡＮＡY7JqjJmDP3
}291Please respect copyright.ＰＥＮＡＮＡyc2gL124QJ
}291Please respect copyright.ＰＥＮＡＮＡiQ4tzT0ZA4
}291Please respect copyright.ＰＥＮＡＮＡRE9y3F2LhZ
}291Please respect copyright.ＰＥＮＡＮＡmZCRxsn2Pk
291Please respect copyright.ＰＥＮＡＮＡi1717ZkvdP
steps++;291Please respect copyright.ＰＥＮＡＮＡ7kFlrJyyhC
}291Please respect copyright.ＰＥＮＡＮＡ2bCJxDr2nr
// If we finish the BFS and did not find end, return -1.291Please respect copyright.ＰＥＮＡＮＡOu5ogrDZb5
return -1;291Please respect copyright.ＰＥＮＡＮＡPBmDpYuWwl
}291Please respect copyright.ＰＥＮＡＮＡBUlNzyK4sG
}
然後按「加至主畫面」