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)212Please respect copyright.ＰＥＮＡＮＡ9BVznwknWW
// better than use DFS as it just need to find out the shortest path.
class Solution {212Please respect copyright.ＰＥＮＡＮＡ7Qz4HOehAj
public int minMutation(String start, String end, String[] bank) {212Please respect copyright.ＰＥＮＡＮＡGsRNsCNm7f
// 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.212Please respect copyright.ＰＥＮＡＮＡJRWekhCTLl
Queue<String> queue = new LinkedList<>();212Please respect copyright.ＰＥＮＡＮＡ4NT1zB7Elj
Set<String> seen = new HashSet<>();212Please respect copyright.ＰＥＮＡＮＡcP5rHWO5y0
queue.add(start);212Please respect copyright.ＰＥＮＡＮＡQaCdiINs3b
seen.add(start);212Please respect copyright.ＰＥＮＡＮＡ9n0kbgg8o7
212Please respect copyright.ＰＥＮＡＮＡ7ppfy07UJM
int steps = 0;212Please respect copyright.ＰＥＮＡＮＡ6F6T8Iljyj
212Please respect copyright.ＰＥＮＡＮＡaDCfdAmZ45
while (!queue.isEmpty()) {212Please respect copyright.ＰＥＮＡＮＡVRigwnP0ck
int nodesInQueue = queue.size();212Please respect copyright.ＰＥＮＡＮＡV4FdyOdhYU
for (int j = 0; j < nodesInQueue; j++) {212Please respect copyright.ＰＥＮＡＮＡj7iblD7PXh
String node = queue.remove();212Please respect copyright.ＰＥＮＡＮＡ8IG9UHrvOb
// 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)) {212Please respect copyright.ＰＥＮＡＮＡ6jMJTnD8JJ
return steps;212Please respect copyright.ＰＥＮＡＮＡK0C3vhksNX
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {212Please respect copyright.ＰＥＮＡＮＡYX4gVuiJZ1
for (int i = 0; i < node.length(); i++) {212Please respect copyright.ＰＥＮＡＮＡxmDZ7oxzwl
String neighbor = node.substring(0, i) + c + node.substring(i + 1);212Please respect copyright.ＰＥＮＡＮＡuTyOSzdPIS
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {212Please respect copyright.ＰＥＮＡＮＡSO7DN5L7Gi
queue.add(neighbor);212Please respect copyright.ＰＥＮＡＮＡZALkTvZS3l
seen.add(neighbor);212Please respect copyright.ＰＥＮＡＮＡtJ2QpDljXP
}212Please respect copyright.ＰＥＮＡＮＡO5ZdjgCol9
}212Please respect copyright.ＰＥＮＡＮＡeIWSP4GOXT
}212Please respect copyright.ＰＥＮＡＮＡ1BwW3VHzBr
}212Please respect copyright.ＰＥＮＡＮＡ39xJNFvS0C
212Please respect copyright.ＰＥＮＡＮＡyWkSr83Dyt
steps++;212Please respect copyright.ＰＥＮＡＮＡ6t1LDoyqW8
}212Please respect copyright.ＰＥＮＡＮＡcK122YHL7Q
// If we finish the BFS and did not find end, return -1.212Please respect copyright.ＰＥＮＡＮＡHwiykVn6Uu
return -1;212Please respect copyright.ＰＥＮＡＮＡuIH9KR6ejK
}212Please respect copyright.ＰＥＮＡＮＡgB8ep5HDda
}
