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)145Please respect copyright.ＰＥＮＡＮＡYar5CzI5ro
// better than use DFS as it just need to find out the shortest path.
class Solution {145Please respect copyright.ＰＥＮＡＮＡS0nXtqhNY0
public int minMutation(String start, String end, String[] bank) {145Please respect copyright.ＰＥＮＡＮＡp9sBo4rQk6
// 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.145Please respect copyright.ＰＥＮＡＮＡ65OeBr8udi
Queue<String> queue = new LinkedList<>();145Please respect copyright.ＰＥＮＡＮＡAEXWGdZ45G
Set<String> seen = new HashSet<>();145Please respect copyright.ＰＥＮＡＮＡ685Kd2KtNz
queue.add(start);145Please respect copyright.ＰＥＮＡＮＡS91kEW43N6
seen.add(start);145Please respect copyright.ＰＥＮＡＮＡwB7eqYUCtl
145Please respect copyright.ＰＥＮＡＮＡrgo4t4yd9S
int steps = 0;145Please respect copyright.ＰＥＮＡＮＡslm0SmIk1F
145Please respect copyright.ＰＥＮＡＮＡcFo4D7wFQ5
while (!queue.isEmpty()) {145Please respect copyright.ＰＥＮＡＮＡeA8uDJIZOV
int nodesInQueue = queue.size();145Please respect copyright.ＰＥＮＡＮＡz3psuB5Jgq
for (int j = 0; j < nodesInQueue; j++) {145Please respect copyright.ＰＥＮＡＮＡn6Lh2wP1fK
String node = queue.remove();145Please respect copyright.ＰＥＮＡＮＡglMEUk9RIS
// 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)) {145Please respect copyright.ＰＥＮＡＮＡ5QU9hwrYrC
return steps;145Please respect copyright.ＰＥＮＡＮＡCOJlNnMyeX
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {145Please respect copyright.ＰＥＮＡＮＡhhVn0xri2O
for (int i = 0; i < node.length(); i++) {145Please respect copyright.ＰＥＮＡＮＡlschSOUC9G
String neighbor = node.substring(0, i) + c + node.substring(i + 1);145Please respect copyright.ＰＥＮＡＮＡ72GiqFBCuk
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {145Please respect copyright.ＰＥＮＡＮＡsxvtSxEtXj
queue.add(neighbor);145Please respect copyright.ＰＥＮＡＮＡ8RBgWMJWJR
seen.add(neighbor);145Please respect copyright.ＰＥＮＡＮＡlKg4JXl9th
}145Please respect copyright.ＰＥＮＡＮＡyu0uJP4h7S
}145Please respect copyright.ＰＥＮＡＮＡNQRmFm6w7h
}145Please respect copyright.ＰＥＮＡＮＡvGoXcEthmp
}145Please respect copyright.ＰＥＮＡＮＡEfmzzmmmdQ
145Please respect copyright.ＰＥＮＡＮＡoPbyTTBTCn
steps++;145Please respect copyright.ＰＥＮＡＮＡ2TzVrP2Pie
}145Please respect copyright.ＰＥＮＡＮＡYs0MaxMB2e
// If we finish the BFS and did not find end, return -1.145Please respect copyright.ＰＥＮＡＮＡQIf00rNMS9
return -1;145Please respect copyright.ＰＥＮＡＮＡriQGXIPBAL
}145Please respect copyright.ＰＥＮＡＮＡNaBua3OZ10
}
