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)265Please respect copyright.ＰＥＮＡＮＡXo2cq8DMUg
// better than use DFS as it just need to find out the shortest path.
class Solution {265Please respect copyright.ＰＥＮＡＮＡ68Palid5hv
public int minMutation(String start, String end, String[] bank) {265Please respect copyright.ＰＥＮＡＮＡUMRBezPxb3
// 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.265Please respect copyright.ＰＥＮＡＮＡOzQhN2A9bx
Queue<String> queue = new LinkedList<>();265Please respect copyright.ＰＥＮＡＮＡwNzIcpqfM6
Set<String> seen = new HashSet<>();265Please respect copyright.ＰＥＮＡＮＡuwLEbvTazI
queue.add(start);265Please respect copyright.ＰＥＮＡＮＡBkihhpwLkv
seen.add(start);265Please respect copyright.ＰＥＮＡＮＡfVETaCN2v9
265Please respect copyright.ＰＥＮＡＮＡJpxf4sD4Lu
int steps = 0;265Please respect copyright.ＰＥＮＡＮＡO0aiOIJV03
265Please respect copyright.ＰＥＮＡＮＡtYFw97LGuj
while (!queue.isEmpty()) {265Please respect copyright.ＰＥＮＡＮＡaP3YVKLaa8
int nodesInQueue = queue.size();265Please respect copyright.ＰＥＮＡＮＡaOn8S4221U
for (int j = 0; j < nodesInQueue; j++) {265Please respect copyright.ＰＥＮＡＮＡrTMOlmpsAd
String node = queue.remove();265Please respect copyright.ＰＥＮＡＮＡBJ41R0h9vU
// 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)) {265Please respect copyright.ＰＥＮＡＮＡhsWEaJzTCx
return steps;265Please respect copyright.ＰＥＮＡＮＡSZYOWCIyne
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {265Please respect copyright.ＰＥＮＡＮＡaubJLCa1ib
for (int i = 0; i < node.length(); i++) {265Please respect copyright.ＰＥＮＡＮＡaoQftss1Zi
String neighbor = node.substring(0, i) + c + node.substring(i + 1);265Please respect copyright.ＰＥＮＡＮＡVdlZ3u9esh
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {265Please respect copyright.ＰＥＮＡＮＡJ4LTsgA042
queue.add(neighbor);265Please respect copyright.ＰＥＮＡＮＡeNsOQWKHPh
seen.add(neighbor);265Please respect copyright.ＰＥＮＡＮＡSQ7SvfF9VF
}265Please respect copyright.ＰＥＮＡＮＡPxPSJpFAqH
}265Please respect copyright.ＰＥＮＡＮＡxztON2mBMK
}265Please respect copyright.ＰＥＮＡＮＡ5ecnH8P4G2
}265Please respect copyright.ＰＥＮＡＮＡRc7ky624E3
265Please respect copyright.ＰＥＮＡＮＡBhj7pDKSJY
steps++;265Please respect copyright.ＰＥＮＡＮＡc9bt6OkZcU
}265Please respect copyright.ＰＥＮＡＮＡK3GUlghAmx
// If we finish the BFS and did not find end, return -1.265Please respect copyright.ＰＥＮＡＮＡyVZwpZRi1k
return -1;265Please respect copyright.ＰＥＮＡＮＡfdF2798QTt
}265Please respect copyright.ＰＥＮＡＮＡsqnWc37c4C
}
