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)237Please respect copyright.ＰＥＮＡＮＡniaLVZtOOW
// better than use DFS as it just need to find out the shortest path.
class Solution {237Please respect copyright.ＰＥＮＡＮＡXAUvSSwQeu
public int minMutation(String start, String end, String[] bank) {237Please respect copyright.ＰＥＮＡＮＡatC3W9oCxB
// 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.237Please respect copyright.ＰＥＮＡＮＡc6BQ7QqyD2
Queue<String> queue = new LinkedList<>();237Please respect copyright.ＰＥＮＡＮＡc9523HkxzR
Set<String> seen = new HashSet<>();237Please respect copyright.ＰＥＮＡＮＡTYQUZhAk6F
queue.add(start);237Please respect copyright.ＰＥＮＡＮＡZdi0k8eAaG
seen.add(start);237Please respect copyright.ＰＥＮＡＮＡATbEBFZtTB
237Please respect copyright.ＰＥＮＡＮＡf2RY16Pfzb
int steps = 0;237Please respect copyright.ＰＥＮＡＮＡkzK3uav67o
237Please respect copyright.ＰＥＮＡＮＡiCkqZamsqO
while (!queue.isEmpty()) {237Please respect copyright.ＰＥＮＡＮＡHACIiFIIGN
int nodesInQueue = queue.size();237Please respect copyright.ＰＥＮＡＮＡpJev2l8N9q
for (int j = 0; j < nodesInQueue; j++) {237Please respect copyright.ＰＥＮＡＮＡvGfVFF2QC3
String node = queue.remove();237Please respect copyright.ＰＥＮＡＮＡNK5fYkfsmh
// 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)) {237Please respect copyright.ＰＥＮＡＮＡB4Iq2kmuWv
return steps;237Please respect copyright.ＰＥＮＡＮＡhunRYLjKS0
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {237Please respect copyright.ＰＥＮＡＮＡ5BPXXMuqEW
for (int i = 0; i < node.length(); i++) {237Please respect copyright.ＰＥＮＡＮＡAPuYKodDRY
String neighbor = node.substring(0, i) + c + node.substring(i + 1);237Please respect copyright.ＰＥＮＡＮＡPc9mZSZLp1
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {237Please respect copyright.ＰＥＮＡＮＡbgfuf7at8m
queue.add(neighbor);237Please respect copyright.ＰＥＮＡＮＡtIL2hLSFg9
seen.add(neighbor);237Please respect copyright.ＰＥＮＡＮＡRyYQYCkxLC
}237Please respect copyright.ＰＥＮＡＮＡ8zWf5eNkOX
}237Please respect copyright.ＰＥＮＡＮＡp2w1OormOx
}237Please respect copyright.ＰＥＮＡＮＡAHqjwqNvSu
}237Please respect copyright.ＰＥＮＡＮＡRjoqpLr1a8
237Please respect copyright.ＰＥＮＡＮＡm1Zj3QkeW0
steps++;237Please respect copyright.ＰＥＮＡＮＡrAhuX2sgZm
}237Please respect copyright.ＰＥＮＡＮＡgLzQWjdqAs
// If we finish the BFS and did not find end, return -1.237Please respect copyright.ＰＥＮＡＮＡz4ozjrk3Kt
return -1;237Please respect copyright.ＰＥＮＡＮＡUdKn4REVeT
}237Please respect copyright.ＰＥＮＡＮＡODJDLquuk0
}
