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)161Please respect copyright.ＰＥＮＡＮＡIguZcCG5T0
// better than use DFS as it just need to find out the shortest path.
class Solution {161Please respect copyright.ＰＥＮＡＮＡqLdkS5fXRb
public int minMutation(String start, String end, String[] bank) {161Please respect copyright.ＰＥＮＡＮＡKi8r4QatAj
// 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.161Please respect copyright.ＰＥＮＡＮＡqFUIK3jKdq
Queue<String> queue = new LinkedList<>();161Please respect copyright.ＰＥＮＡＮＡdz4W04mC3Q
Set<String> seen = new HashSet<>();161Please respect copyright.ＰＥＮＡＮＡFGCGGMLDBe
queue.add(start);161Please respect copyright.ＰＥＮＡＮＡgkuvJgyYHY
seen.add(start);161Please respect copyright.ＰＥＮＡＮＡ7ZTblV6b77
161Please respect copyright.ＰＥＮＡＮＡawqfnzM70p
int steps = 0;161Please respect copyright.ＰＥＮＡＮＡg8ShcVsYKE
161Please respect copyright.ＰＥＮＡＮＡHATdB86qI8
while (!queue.isEmpty()) {161Please respect copyright.ＰＥＮＡＮＡk9Ylfb3qNA
int nodesInQueue = queue.size();161Please respect copyright.ＰＥＮＡＮＡurlAlg8rZs
for (int j = 0; j < nodesInQueue; j++) {161Please respect copyright.ＰＥＮＡＮＡqbId6PUzI0
String node = queue.remove();161Please respect copyright.ＰＥＮＡＮＡ4sO8Vui7eb
// 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)) {161Please respect copyright.ＰＥＮＡＮＡW4FZ19yvqR
return steps;161Please respect copyright.ＰＥＮＡＮＡa9lmSgqCYx
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {161Please respect copyright.ＰＥＮＡＮＡd9C4bavniS
for (int i = 0; i < node.length(); i++) {161Please respect copyright.ＰＥＮＡＮＡyRQ2FyTlDn
String neighbor = node.substring(0, i) + c + node.substring(i + 1);161Please respect copyright.ＰＥＮＡＮＡ3xrEnxggn8
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {161Please respect copyright.ＰＥＮＡＮＡguwlRt1mty
queue.add(neighbor);161Please respect copyright.ＰＥＮＡＮＡruVibkDGLs
seen.add(neighbor);161Please respect copyright.ＰＥＮＡＮＡSMi9MDuVPU
}161Please respect copyright.ＰＥＮＡＮＡmgZYnj22EP
}161Please respect copyright.ＰＥＮＡＮＡuK7dmVnueb
}161Please respect copyright.ＰＥＮＡＮＡ9nfLyo0lOG
}161Please respect copyright.ＰＥＮＡＮＡqB6coOnQfF
161Please respect copyright.ＰＥＮＡＮＡ0q1YzTxtjY
steps++;161Please respect copyright.ＰＥＮＡＮＡCijpHK5NnG
}161Please respect copyright.ＰＥＮＡＮＡLV114pC3xo
// If we finish the BFS and did not find end, return -1.161Please respect copyright.ＰＥＮＡＮＡnbTlqtkMuH
return -1;161Please respect copyright.ＰＥＮＡＮＡIBVL7BowBp
}161Please respect copyright.ＰＥＮＡＮＡaflCruX9iN
}
