x
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)193Please respect copyright.ＰＥＮＡＮＡYo62wYmDSm
// better than use DFS as it just need to find out the shortest path.
class Solution {193Please respect copyright.ＰＥＮＡＮＡsKCM5mIzjj
public int minMutation(String start, String end, String[] bank) {193Please respect copyright.ＰＥＮＡＮＡf9BQCavht4
// 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.193Please respect copyright.ＰＥＮＡＮＡZvao512rr3
Queue<String> queue = new LinkedList<>();193Please respect copyright.ＰＥＮＡＮＡUepeAMvFf5
Set<String> seen = new HashSet<>();193Please respect copyright.ＰＥＮＡＮＡgVKrBWiKjY
queue.add(start);193Please respect copyright.ＰＥＮＡＮＡjh7a2MarXB
seen.add(start);193Please respect copyright.ＰＥＮＡＮＡ8bqX6rpLIO
193Please respect copyright.ＰＥＮＡＮＡ9Lo2Oc8Arp
int steps = 0;193Please respect copyright.ＰＥＮＡＮＡl6n3h3Ybwv
193Please respect copyright.ＰＥＮＡＮＡiRIxvgMA5J
while (!queue.isEmpty()) {193Please respect copyright.ＰＥＮＡＮＡNH1Y9d3eSq
int nodesInQueue = queue.size();193Please respect copyright.ＰＥＮＡＮＡrxDnYucuhE
for (int j = 0; j < nodesInQueue; j++) {193Please respect copyright.ＰＥＮＡＮＡ7vAmIUPEz7
String node = queue.remove();193Please respect copyright.ＰＥＮＡＮＡYo93WJQJKL
// 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)) {193Please respect copyright.ＰＥＮＡＮＡVVIYJxq9oO
return steps;193Please respect copyright.ＰＥＮＡＮＡpChez51Z2z
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {193Please respect copyright.ＰＥＮＡＮＡnE0GkDYzJG
for (int i = 0; i < node.length(); i++) {193Please respect copyright.ＰＥＮＡＮＡdPvGJLOJCj
String neighbor = node.substring(0, i) + c + node.substring(i + 1);193Please respect copyright.ＰＥＮＡＮＡpQD8VYrUo5
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {193Please respect copyright.ＰＥＮＡＮＡlbBa1Y27D0
queue.add(neighbor);193Please respect copyright.ＰＥＮＡＮＡnL76U51R3o
seen.add(neighbor);193Please respect copyright.ＰＥＮＡＮＡRuFkmJhlzz
}193Please respect copyright.ＰＥＮＡＮＡBj2MmQo3y5
}193Please respect copyright.ＰＥＮＡＮＡ5x8jNNofJd
}193Please respect copyright.ＰＥＮＡＮＡnbKzQkASet
}193Please respect copyright.ＰＥＮＡＮＡBWlVMNjThC
193Please respect copyright.ＰＥＮＡＮＡH0n6WtsfxT
steps++;193Please respect copyright.ＰＥＮＡＮＡepfWY7y779
}193Please respect copyright.ＰＥＮＡＮＡv95RpLa4I8
// If we finish the BFS and did not find end, return -1.193Please respect copyright.ＰＥＮＡＮＡ4P3rEZrhpU
return -1;193Please respect copyright.ＰＥＮＡＮＡVCmS3ZwGwX
}193Please respect copyright.ＰＥＮＡＮＡxWlWDcl2xC
}
