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)195Please respect copyright.ＰＥＮＡＮＡm4QBb4l3Nd
// better than use DFS as it just need to find out the shortest path.
class Solution {195Please respect copyright.ＰＥＮＡＮＡpSWoXNNBl7
public int minMutation(String start, String end, String[] bank) {195Please respect copyright.ＰＥＮＡＮＡueufbIvvmd
// 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.195Please respect copyright.ＰＥＮＡＮＡ8fvNL4FnZD
Queue<String> queue = new LinkedList<>();195Please respect copyright.ＰＥＮＡＮＡvDiJyisn06
Set<String> seen = new HashSet<>();195Please respect copyright.ＰＥＮＡＮＡS0Ni6ykonV
queue.add(start);195Please respect copyright.ＰＥＮＡＮＡHnepYPbwgK
seen.add(start);195Please respect copyright.ＰＥＮＡＮＡZfBrm3VqNA
195Please respect copyright.ＰＥＮＡＮＡBZ52k4ppd6
int steps = 0;195Please respect copyright.ＰＥＮＡＮＡuHMUR2cQtt
195Please respect copyright.ＰＥＮＡＮＡaI3CFjOJi5
while (!queue.isEmpty()) {195Please respect copyright.ＰＥＮＡＮＡrLvPVMBeeK
int nodesInQueue = queue.size();195Please respect copyright.ＰＥＮＡＮＡ3lVwiMKPbH
for (int j = 0; j < nodesInQueue; j++) {195Please respect copyright.ＰＥＮＡＮＡ4AHhvrSBP1
String node = queue.remove();195Please respect copyright.ＰＥＮＡＮＡny3W6UvgBe
// 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)) {195Please respect copyright.ＰＥＮＡＮＡ0UILYDVeV1
return steps;195Please respect copyright.ＰＥＮＡＮＡ3JQAuB0wrY
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {195Please respect copyright.ＰＥＮＡＮＡYbyFnRGsnQ
for (int i = 0; i < node.length(); i++) {195Please respect copyright.ＰＥＮＡＮＡh6TAoWqiKZ
String neighbor = node.substring(0, i) + c + node.substring(i + 1);195Please respect copyright.ＰＥＮＡＮＡmXRLtwGUWi
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {195Please respect copyright.ＰＥＮＡＮＡjCJK2XdpFg
queue.add(neighbor);195Please respect copyright.ＰＥＮＡＮＡ2SA3Q10nwB
seen.add(neighbor);195Please respect copyright.ＰＥＮＡＮＡ5fDX0TQcEf
}195Please respect copyright.ＰＥＮＡＮＡsAfwBWSvpH
}195Please respect copyright.ＰＥＮＡＮＡBOfR8tAW4M
}195Please respect copyright.ＰＥＮＡＮＡDKEYX29B6k
}195Please respect copyright.ＰＥＮＡＮＡCxkLe1Nwci
195Please respect copyright.ＰＥＮＡＮＡ5IQfAWUjTj
steps++;195Please respect copyright.ＰＥＮＡＮＡjQzqseIfpz
}195Please respect copyright.ＰＥＮＡＮＡ9NlaakcJhK
// If we finish the BFS and did not find end, return -1.195Please respect copyright.ＰＥＮＡＮＡAG8Rz2Vf4G
return -1;195Please respect copyright.ＰＥＮＡＮＡyBscPsACRd
}195Please respect copyright.ＰＥＮＡＮＡyaBqP997ch
}
