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)216Please respect copyright.ＰＥＮＡＮＡGF6XchXApg
// better than use DFS as it just need to find out the shortest path.
class Solution {216Please respect copyright.ＰＥＮＡＮＡgnSrQ42Oln
public int minMutation(String start, String end, String[] bank) {216Please respect copyright.ＰＥＮＡＮＡLybgrlFtez
// 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.216Please respect copyright.ＰＥＮＡＮＡaMojRczkKZ
Queue<String> queue = new LinkedList<>();216Please respect copyright.ＰＥＮＡＮＡ6uCLjOpuXn
Set<String> seen = new HashSet<>();216Please respect copyright.ＰＥＮＡＮＡrNFQ5hcORI
queue.add(start);216Please respect copyright.ＰＥＮＡＮＡeB9foiR2FN
seen.add(start);216Please respect copyright.ＰＥＮＡＮＡvjw1OX2LqN
216Please respect copyright.ＰＥＮＡＮＡUWZpTLFOY3
int steps = 0;216Please respect copyright.ＰＥＮＡＮＡMC0jOeClZn
216Please respect copyright.ＰＥＮＡＮＡbbdijZhkTJ
while (!queue.isEmpty()) {216Please respect copyright.ＰＥＮＡＮＡsqmNZJpDPt
int nodesInQueue = queue.size();216Please respect copyright.ＰＥＮＡＮＡKbG1Xso4fO
for (int j = 0; j < nodesInQueue; j++) {216Please respect copyright.ＰＥＮＡＮＡiageGpiDdm
String node = queue.remove();216Please respect copyright.ＰＥＮＡＮＡU0neJpBSwN
// 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)) {216Please respect copyright.ＰＥＮＡＮＡat7ZXUdZdt
return steps;216Please respect copyright.ＰＥＮＡＮＡTBg56w68FN
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {216Please respect copyright.ＰＥＮＡＮＡoPBBlL8WJ6
for (int i = 0; i < node.length(); i++) {216Please respect copyright.ＰＥＮＡＮＡgiRXhc3fvg
String neighbor = node.substring(0, i) + c + node.substring(i + 1);216Please respect copyright.ＰＥＮＡＮＡ0JNqZEf5l4
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {216Please respect copyright.ＰＥＮＡＮＡRpt0BQjGh5
queue.add(neighbor);216Please respect copyright.ＰＥＮＡＮＡpX29fp3FQz
seen.add(neighbor);216Please respect copyright.ＰＥＮＡＮＡthkpW6UcR3
}216Please respect copyright.ＰＥＮＡＮＡOXZthEBV4A
}216Please respect copyright.ＰＥＮＡＮＡlVLEj1pcwi
}216Please respect copyright.ＰＥＮＡＮＡrRvLRUQk6g
}216Please respect copyright.ＰＥＮＡＮＡwgyZUxijRc
216Please respect copyright.ＰＥＮＡＮＡTlfLvBoDIC
steps++;216Please respect copyright.ＰＥＮＡＮＡnJiC0snyrr
}216Please respect copyright.ＰＥＮＡＮＡ4kgOvZqe6r
// If we finish the BFS and did not find end, return -1.216Please respect copyright.ＰＥＮＡＮＡiMW18qC2pC
return -1;216Please respect copyright.ＰＥＮＡＮＡoeENa6s1LI
}216Please respect copyright.ＰＥＮＡＮＡgsjkI4j7pI
}
然後按「加至主畫面」