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)201Please respect copyright.ＰＥＮＡＮＡnCg3YBK9yF
// better than use DFS as it just need to find out the shortest path.
class Solution {201Please respect copyright.ＰＥＮＡＮＡeVWwHTxWFJ
public int minMutation(String start, String end, String[] bank) {201Please respect copyright.ＰＥＮＡＮＡr93ND8y2sE
// 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.201Please respect copyright.ＰＥＮＡＮＡ6gbxSO49q4
Queue<String> queue = new LinkedList<>();201Please respect copyright.ＰＥＮＡＮＡERm6LqZO7s
Set<String> seen = new HashSet<>();201Please respect copyright.ＰＥＮＡＮＡO1uJnmXUNl
queue.add(start);201Please respect copyright.ＰＥＮＡＮＡtQVRpmRHxn
seen.add(start);201Please respect copyright.ＰＥＮＡＮＡ7Jtxv8pBSJ
201Please respect copyright.ＰＥＮＡＮＡjwKj3321Jo
int steps = 0;201Please respect copyright.ＰＥＮＡＮＡA0I2cBeDdo
201Please respect copyright.ＰＥＮＡＮＡc5VLlK1fI1
while (!queue.isEmpty()) {201Please respect copyright.ＰＥＮＡＮＡIVi0sG7OZ2
int nodesInQueue = queue.size();201Please respect copyright.ＰＥＮＡＮＡOI6IUrWaMM
for (int j = 0; j < nodesInQueue; j++) {201Please respect copyright.ＰＥＮＡＮＡN99hw1cWNX
String node = queue.remove();201Please respect copyright.ＰＥＮＡＮＡ9HiOO1cFnG
// 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)) {201Please respect copyright.ＰＥＮＡＮＡvgL7Lq1U1c
return steps;201Please respect copyright.ＰＥＮＡＮＡVpJhNhN1PC
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {201Please respect copyright.ＰＥＮＡＮＡbqfQfCD0CN
for (int i = 0; i < node.length(); i++) {201Please respect copyright.ＰＥＮＡＮＡ5lJA3PRi6D
String neighbor = node.substring(0, i) + c + node.substring(i + 1);201Please respect copyright.ＰＥＮＡＮＡZWlt0J37X2
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {201Please respect copyright.ＰＥＮＡＮＡNm5Cu6smz0
queue.add(neighbor);201Please respect copyright.ＰＥＮＡＮＡ4TGRcnXviA
seen.add(neighbor);201Please respect copyright.ＰＥＮＡＮＡh6gQngQic5
}201Please respect copyright.ＰＥＮＡＮＡSNeHB52LwE
}201Please respect copyright.ＰＥＮＡＮＡcvUTurcJP1
}201Please respect copyright.ＰＥＮＡＮＡdYn1nT2BO4
}201Please respect copyright.ＰＥＮＡＮＡRbr67LDzDl
201Please respect copyright.ＰＥＮＡＮＡmj1adUITL0
steps++;201Please respect copyright.ＰＥＮＡＮＡprAts1gr0D
}201Please respect copyright.ＰＥＮＡＮＡ2fT4rWfQvW
// If we finish the BFS and did not find end, return -1.201Please respect copyright.ＰＥＮＡＮＡX9B1NshxW3
return -1;201Please respect copyright.ＰＥＮＡＮＡ2pmflAFuw7
}201Please respect copyright.ＰＥＮＡＮＡJ1eEemNYUB
}
