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)255Please respect copyright.ＰＥＮＡＮＡuJc0IWfTpm
// better than use DFS as it just need to find out the shortest path.
class Solution {255Please respect copyright.ＰＥＮＡＮＡpv8vlKpds9
public int minMutation(String start, String end, String[] bank) {255Please respect copyright.ＰＥＮＡＮＡOjs5TCKn0g
// 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.255Please respect copyright.ＰＥＮＡＮＡghW8eH9pK5
Queue<String> queue = new LinkedList<>();255Please respect copyright.ＰＥＮＡＮＡBPMKzUExCR
Set<String> seen = new HashSet<>();255Please respect copyright.ＰＥＮＡＮＡSZy7BOBHUT
queue.add(start);255Please respect copyright.ＰＥＮＡＮＡC134MDDpjO
seen.add(start);255Please respect copyright.ＰＥＮＡＮＡ2wBKx9BGor
255Please respect copyright.ＰＥＮＡＮＡAE7EgGaank
int steps = 0;255Please respect copyright.ＰＥＮＡＮＡK39s0sVG1j
255Please respect copyright.ＰＥＮＡＮＡEbEYJ2ddpZ
while (!queue.isEmpty()) {255Please respect copyright.ＰＥＮＡＮＡ0WLuPG4H1M
int nodesInQueue = queue.size();255Please respect copyright.ＰＥＮＡＮＡnjkUKYG5sn
for (int j = 0; j < nodesInQueue; j++) {255Please respect copyright.ＰＥＮＡＮＡyN9MdzRfvs
String node = queue.remove();255Please respect copyright.ＰＥＮＡＮＡ7woLbYXUwm
// 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)) {255Please respect copyright.ＰＥＮＡＮＡxdANP5yHUT
return steps;255Please respect copyright.ＰＥＮＡＮＡLLSfZMqbsE
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {255Please respect copyright.ＰＥＮＡＮＡjKkm0eW9LT
for (int i = 0; i < node.length(); i++) {255Please respect copyright.ＰＥＮＡＮＡWIGu4UTXCL
String neighbor = node.substring(0, i) + c + node.substring(i + 1);255Please respect copyright.ＰＥＮＡＮＡoiA9R4mhsp
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {255Please respect copyright.ＰＥＮＡＮＡwIScSxo21Y
queue.add(neighbor);255Please respect copyright.ＰＥＮＡＮＡwXkFQ1T3i3
seen.add(neighbor);255Please respect copyright.ＰＥＮＡＮＡTG5uTCljOV
}255Please respect copyright.ＰＥＮＡＮＡduoNg9F3mD
}255Please respect copyright.ＰＥＮＡＮＡguQW1FntQM
}255Please respect copyright.ＰＥＮＡＮＡRfTRhiqiG7
}255Please respect copyright.ＰＥＮＡＮＡHVlAcECiwg
255Please respect copyright.ＰＥＮＡＮＡs6MpsxWmn5
steps++;255Please respect copyright.ＰＥＮＡＮＡkSWZi2I1Iw
}255Please respect copyright.ＰＥＮＡＮＡBHXzoi4teA
// If we finish the BFS and did not find end, return -1.255Please respect copyright.ＰＥＮＡＮＡNhLsIftrR1
return -1;255Please respect copyright.ＰＥＮＡＮＡ75J2LskBuc
}255Please respect copyright.ＰＥＮＡＮＡhaT9VQRUi8
}
然後按「加至主畫面」