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)253Please respect copyright.ＰＥＮＡＮＡJosgRixiL4
// better than use DFS as it just need to find out the shortest path.
class Solution {253Please respect copyright.ＰＥＮＡＮＡk6qKJ5o849
public int minMutation(String start, String end, String[] bank) {253Please respect copyright.ＰＥＮＡＮＡxH4G79ImaV
// 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.253Please respect copyright.ＰＥＮＡＮＡG95ZpR16WU
Queue<String> queue = new LinkedList<>();253Please respect copyright.ＰＥＮＡＮＡCZbXKnTJJQ
Set<String> seen = new HashSet<>();253Please respect copyright.ＰＥＮＡＮＡ2T5s4Bi1wW
queue.add(start);253Please respect copyright.ＰＥＮＡＮＡGtAwTKeu1b
seen.add(start);253Please respect copyright.ＰＥＮＡＮＡ4Foao7qMaa
253Please respect copyright.ＰＥＮＡＮＡuWs8bHscFF
int steps = 0;253Please respect copyright.ＰＥＮＡＮＡ7TAiLrm0CV
253Please respect copyright.ＰＥＮＡＮＡ6r29PYnvXp
while (!queue.isEmpty()) {253Please respect copyright.ＰＥＮＡＮＡyDElHj5NQr
int nodesInQueue = queue.size();253Please respect copyright.ＰＥＮＡＮＡhcvQEBi4He
for (int j = 0; j < nodesInQueue; j++) {253Please respect copyright.ＰＥＮＡＮＡiS7Zl59wde
String node = queue.remove();253Please respect copyright.ＰＥＮＡＮＡw3SUrJTWRv
// 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)) {253Please respect copyright.ＰＥＮＡＮＡuf6hJUNQQu
return steps;253Please respect copyright.ＰＥＮＡＮＡfAVqyj1HfH
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {253Please respect copyright.ＰＥＮＡＮＡTHqgJBn0qV
for (int i = 0; i < node.length(); i++) {253Please respect copyright.ＰＥＮＡＮＡR8wWDbW3pf
String neighbor = node.substring(0, i) + c + node.substring(i + 1);253Please respect copyright.ＰＥＮＡＮＡfY673E8qf4
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {253Please respect copyright.ＰＥＮＡＮＡrBIgm0D3vT
queue.add(neighbor);253Please respect copyright.ＰＥＮＡＮＡ54UufWE7PG
seen.add(neighbor);253Please respect copyright.ＰＥＮＡＮＡEIXPm88vx1
}253Please respect copyright.ＰＥＮＡＮＡT09ljfQCbG
}253Please respect copyright.ＰＥＮＡＮＡkwaFvAC4d7
}253Please respect copyright.ＰＥＮＡＮＡ7mBzKlX0U6
}253Please respect copyright.ＰＥＮＡＮＡ0VAOxrFyD4
253Please respect copyright.ＰＥＮＡＮＡDo5unHdKq7
steps++;253Please respect copyright.ＰＥＮＡＮＡRJYBuaRWQQ
}253Please respect copyright.ＰＥＮＡＮＡRb5ru18uaX
// If we finish the BFS and did not find end, return -1.253Please respect copyright.ＰＥＮＡＮＡsLSo73CqnV
return -1;253Please respect copyright.ＰＥＮＡＮＡdVIs66jNTQ
}253Please respect copyright.ＰＥＮＡＮＡNh1mIjoTa1
}
