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)240Please respect copyright.ＰＥＮＡＮＡsUDVkLlmlR
// better than use DFS as it just need to find out the shortest path.
class Solution {240Please respect copyright.ＰＥＮＡＮＡOOUpa9H2Da
public int minMutation(String start, String end, String[] bank) {240Please respect copyright.ＰＥＮＡＮＡLKXieJmMXg
// 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.240Please respect copyright.ＰＥＮＡＮＡH4yTu0457M
Queue<String> queue = new LinkedList<>();240Please respect copyright.ＰＥＮＡＮＡe8l3wefMOh
Set<String> seen = new HashSet<>();240Please respect copyright.ＰＥＮＡＮＡDE75nZI9rz
queue.add(start);240Please respect copyright.ＰＥＮＡＮＡpBwCUIfAaw
seen.add(start);240Please respect copyright.ＰＥＮＡＮＡtPtWvIEKEi
240Please respect copyright.ＰＥＮＡＮＡSiuoR0M1DS
int steps = 0;240Please respect copyright.ＰＥＮＡＮＡs1gnd68UJW
240Please respect copyright.ＰＥＮＡＮＡVZrGXk8B27
while (!queue.isEmpty()) {240Please respect copyright.ＰＥＮＡＮＡNs1isUzPR3
int nodesInQueue = queue.size();240Please respect copyright.ＰＥＮＡＮＡgMGxOHadia
for (int j = 0; j < nodesInQueue; j++) {240Please respect copyright.ＰＥＮＡＮＡnlOEhOkPAN
String node = queue.remove();240Please respect copyright.ＰＥＮＡＮＡSSBkqCtGyk
// 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)) {240Please respect copyright.ＰＥＮＡＮＡ9OLo4bX4XR
return steps;240Please respect copyright.ＰＥＮＡＮＡ9DABekuqYV
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {240Please respect copyright.ＰＥＮＡＮＡunr765TtKn
for (int i = 0; i < node.length(); i++) {240Please respect copyright.ＰＥＮＡＮＡXLQ2ZQ3WHU
String neighbor = node.substring(0, i) + c + node.substring(i + 1);240Please respect copyright.ＰＥＮＡＮＡXpAsQv1cxQ
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {240Please respect copyright.ＰＥＮＡＮＡclg0AkfYlG
queue.add(neighbor);240Please respect copyright.ＰＥＮＡＮＡ3xf3mW8B43
seen.add(neighbor);240Please respect copyright.ＰＥＮＡＮＡp8ILqpMp0a
}240Please respect copyright.ＰＥＮＡＮＡ7SzoYpgkpG
}240Please respect copyright.ＰＥＮＡＮＡ0CLtlMtAKi
}240Please respect copyright.ＰＥＮＡＮＡWUcLcPILRE
}240Please respect copyright.ＰＥＮＡＮＡJwEwZUyHTF
240Please respect copyright.ＰＥＮＡＮＡihkAp5Ob3i
steps++;240Please respect copyright.ＰＥＮＡＮＡMrjubLpxRO
}240Please respect copyright.ＰＥＮＡＮＡb011Pf6rWH
// If we finish the BFS and did not find end, return -1.240Please respect copyright.ＰＥＮＡＮＡHPrfa3enC6
return -1;240Please respect copyright.ＰＥＮＡＮＡ5gwI9U97dU
}240Please respect copyright.ＰＥＮＡＮＡZhrodOCgcU
}
然後按「加至主畫面」