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)206Please respect copyright.ＰＥＮＡＮＡFhKNn7aBTj
// better than use DFS as it just need to find out the shortest path.
class Solution {206Please respect copyright.ＰＥＮＡＮＡoUMGQreHfC
public int minMutation(String start, String end, String[] bank) {206Please respect copyright.ＰＥＮＡＮＡt07K0nxDXu
// 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.206Please respect copyright.ＰＥＮＡＮＡoomhltSjS8
Queue<String> queue = new LinkedList<>();206Please respect copyright.ＰＥＮＡＮＡnvRKNMcrUO
Set<String> seen = new HashSet<>();206Please respect copyright.ＰＥＮＡＮＡKMQJgPfbxm
queue.add(start);206Please respect copyright.ＰＥＮＡＮＡipUO7fyUk8
seen.add(start);206Please respect copyright.ＰＥＮＡＮＡLDBhRFNTux
206Please respect copyright.ＰＥＮＡＮＡq6rXHyTTAE
int steps = 0;206Please respect copyright.ＰＥＮＡＮＡqo0jyo0dzn
206Please respect copyright.ＰＥＮＡＮＡ1vK6CyNWx4
while (!queue.isEmpty()) {206Please respect copyright.ＰＥＮＡＮＡaCVBBfgcoM
int nodesInQueue = queue.size();206Please respect copyright.ＰＥＮＡＮＡiO8Vv4qFyC
for (int j = 0; j < nodesInQueue; j++) {206Please respect copyright.ＰＥＮＡＮＡwxxPtTYtvu
String node = queue.remove();206Please respect copyright.ＰＥＮＡＮＡtV7T65m3Th
// 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)) {206Please respect copyright.ＰＥＮＡＮＡ2frF63Aqt3
return steps;206Please respect copyright.ＰＥＮＡＮＡCKATbj9m24
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {206Please respect copyright.ＰＥＮＡＮＡVnz6FQE2RJ
for (int i = 0; i < node.length(); i++) {206Please respect copyright.ＰＥＮＡＮＡwqDdFTu8Tv
String neighbor = node.substring(0, i) + c + node.substring(i + 1);206Please respect copyright.ＰＥＮＡＮＡtykuShGiI1
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {206Please respect copyright.ＰＥＮＡＮＡ0u3qPxh7qm
queue.add(neighbor);206Please respect copyright.ＰＥＮＡＮＡ2tgxHU3nMh
seen.add(neighbor);206Please respect copyright.ＰＥＮＡＮＡ8q7LpOhvun
}206Please respect copyright.ＰＥＮＡＮＡv4mnjvN8fN
}206Please respect copyright.ＰＥＮＡＮＡEvx5S0FceH
}206Please respect copyright.ＰＥＮＡＮＡ865NmOXG8M
}206Please respect copyright.ＰＥＮＡＮＡOA3TYSitHk
206Please respect copyright.ＰＥＮＡＮＡ5UbdXrG3y8
steps++;206Please respect copyright.ＰＥＮＡＮＡNaId8favvu
}206Please respect copyright.ＰＥＮＡＮＡFjeaoHvG1x
// If we finish the BFS and did not find end, return -1.206Please respect copyright.ＰＥＮＡＮＡRyqLqUKeCd
return -1;206Please respect copyright.ＰＥＮＡＮＡcP5ophI2ah
}206Please respect copyright.ＰＥＮＡＮＡ72l49SKkw7
}
