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)426Please respect copyright.ＰＥＮＡＮＡLA2DTiQeaM
// better than use DFS as it just need to find out the shortest path.
class Solution {426Please respect copyright.ＰＥＮＡＮＡoSLpGOPJx5
public int minMutation(String start, String end, String[] bank) {426Please respect copyright.ＰＥＮＡＮＡMsZ80SqWlP
// 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.426Please respect copyright.ＰＥＮＡＮＡHt66dGtBSZ
Queue<String> queue = new LinkedList<>();426Please respect copyright.ＰＥＮＡＮＡeDoiCAUxGM
Set<String> seen = new HashSet<>();426Please respect copyright.ＰＥＮＡＮＡYEY4iSJ9e0
queue.add(start);426Please respect copyright.ＰＥＮＡＮＡBKWnNA8CRv
seen.add(start);426Please respect copyright.ＰＥＮＡＮＡKsDtVJSGzR
426Please respect copyright.ＰＥＮＡＮＡhLkoLDc4ZC
int steps = 0;426Please respect copyright.ＰＥＮＡＮＡImhqRIGZkr
426Please respect copyright.ＰＥＮＡＮＡidtYhnK1if
while (!queue.isEmpty()) {426Please respect copyright.ＰＥＮＡＮＡl2wogrWv6s
int nodesInQueue = queue.size();426Please respect copyright.ＰＥＮＡＮＡSzv3n39S9m
for (int j = 0; j < nodesInQueue; j++) {426Please respect copyright.ＰＥＮＡＮＡa6x76nNXQU
String node = queue.remove();426Please respect copyright.ＰＥＮＡＮＡVcKjvFvcH7
// 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)) {426Please respect copyright.ＰＥＮＡＮＡOdd8oBdmTV
return steps;426Please respect copyright.ＰＥＮＡＮＡluPSruqewN
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {426Please respect copyright.ＰＥＮＡＮＡjQBpBs47Ie
for (int i = 0; i < node.length(); i++) {426Please respect copyright.ＰＥＮＡＮＡqloqYL7xc3
String neighbor = node.substring(0, i) + c + node.substring(i + 1);426Please respect copyright.ＰＥＮＡＮＡoXT2dGsvvz
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {426Please respect copyright.ＰＥＮＡＮＡAbSTYsQ7yT
queue.add(neighbor);426Please respect copyright.ＰＥＮＡＮＡkElDs5HYMK
seen.add(neighbor);426Please respect copyright.ＰＥＮＡＮＡymaQAhNI49
}426Please respect copyright.ＰＥＮＡＮＡSAbukhu5ln
}426Please respect copyright.ＰＥＮＡＮＡsdYWuoprmj
}426Please respect copyright.ＰＥＮＡＮＡh6eKrelNbC
}426Please respect copyright.ＰＥＮＡＮＡdMsLzAbZn0
426Please respect copyright.ＰＥＮＡＮＡ4yh9WAN7cp
steps++;426Please respect copyright.ＰＥＮＡＮＡheSm9p10Xo
}426Please respect copyright.ＰＥＮＡＮＡ9vFsWMqIbY
// If we finish the BFS and did not find end, return -1.426Please respect copyright.ＰＥＮＡＮＡesVwO6UPYq
return -1;426Please respect copyright.ＰＥＮＡＮＡIQIt7Mpu5y
}426Please respect copyright.ＰＥＮＡＮＡNVh0ORIXcL
}
and then Add to home screen.