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)159Please respect copyright.ＰＥＮＡＮＡVjpCLJMfEH
// better than use DFS as it just need to find out the shortest path.
class Solution {159Please respect copyright.ＰＥＮＡＮＡZcOJQNRsIj
public int minMutation(String start, String end, String[] bank) {159Please respect copyright.ＰＥＮＡＮＡ6e1lJSVzHC
// 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.159Please respect copyright.ＰＥＮＡＮＡ3JXvIKpUk0
Queue<String> queue = new LinkedList<>();159Please respect copyright.ＰＥＮＡＮＡ5SirMhceA4
Set<String> seen = new HashSet<>();159Please respect copyright.ＰＥＮＡＮＡlOL74BneFC
queue.add(start);159Please respect copyright.ＰＥＮＡＮＡP8NKYCnRdk
seen.add(start);159Please respect copyright.ＰＥＮＡＮＡXGyOuDsIqJ
159Please respect copyright.ＰＥＮＡＮＡ7P1iXNfWlY
int steps = 0;159Please respect copyright.ＰＥＮＡＮＡAkdlTK0tna
159Please respect copyright.ＰＥＮＡＮＡm0kGbFuZqj
while (!queue.isEmpty()) {159Please respect copyright.ＰＥＮＡＮＡbZGmWZvEug
int nodesInQueue = queue.size();159Please respect copyright.ＰＥＮＡＮＡxN4R2iMYHP
for (int j = 0; j < nodesInQueue; j++) {159Please respect copyright.ＰＥＮＡＮＡfW9SPDxfJD
String node = queue.remove();159Please respect copyright.ＰＥＮＡＮＡJZWSap6Fzc
// 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)) {159Please respect copyright.ＰＥＮＡＮＡJz6hADzbgY
return steps;159Please respect copyright.ＰＥＮＡＮＡiFTRrCRgwJ
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {159Please respect copyright.ＰＥＮＡＮＡIloLPC307T
for (int i = 0; i < node.length(); i++) {159Please respect copyright.ＰＥＮＡＮＡXqa1PGz2dY
String neighbor = node.substring(0, i) + c + node.substring(i + 1);159Please respect copyright.ＰＥＮＡＮＡKXy6oeyL0o
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {159Please respect copyright.ＰＥＮＡＮＡB6OGFzKntq
queue.add(neighbor);159Please respect copyright.ＰＥＮＡＮＡDaQmhTS4qv
seen.add(neighbor);159Please respect copyright.ＰＥＮＡＮＡ2ZI4FCsWZK
}159Please respect copyright.ＰＥＮＡＮＡSAqOVcn4Zs
}159Please respect copyright.ＰＥＮＡＮＡmaVZRfMtOs
}159Please respect copyright.ＰＥＮＡＮＡcSlTPKMglg
}159Please respect copyright.ＰＥＮＡＮＡdtQiVlJmNb
159Please respect copyright.ＰＥＮＡＮＡRsYaXMfUNm
steps++;159Please respect copyright.ＰＥＮＡＮＡwqnPeA8VDZ
}159Please respect copyright.ＰＥＮＡＮＡNyDtm8WbpO
// If we finish the BFS and did not find end, return -1.159Please respect copyright.ＰＥＮＡＮＡwIVnjz02ss
return -1;159Please respect copyright.ＰＥＮＡＮＡTELdoaVCZM
}159Please respect copyright.ＰＥＮＡＮＡONvNd6gzih
}
