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)251Please respect copyright.ＰＥＮＡＮＡOMqaz6kGEr
// better than use DFS as it just need to find out the shortest path.
class Solution {251Please respect copyright.ＰＥＮＡＮＡNIBWRIT25A
public int minMutation(String start, String end, String[] bank) {251Please respect copyright.ＰＥＮＡＮＡwdAMf0rr7h
// 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.251Please respect copyright.ＰＥＮＡＮＡqG23ZxQaTl
Queue<String> queue = new LinkedList<>();251Please respect copyright.ＰＥＮＡＮＡ41AZdJSQv7
Set<String> seen = new HashSet<>();251Please respect copyright.ＰＥＮＡＮＡe4AhTIEhrK
queue.add(start);251Please respect copyright.ＰＥＮＡＮＡ5rwjgsBCPl
seen.add(start);251Please respect copyright.ＰＥＮＡＮＡ1OMU4mVTZi
251Please respect copyright.ＰＥＮＡＮＡov2zBBRUfl
int steps = 0;251Please respect copyright.ＰＥＮＡＮＡWVd9y1c0pS
251Please respect copyright.ＰＥＮＡＮＡwQUNSzEVVg
while (!queue.isEmpty()) {251Please respect copyright.ＰＥＮＡＮＡKI8zeZqtbg
int nodesInQueue = queue.size();251Please respect copyright.ＰＥＮＡＮＡDYSDTSLbaY
for (int j = 0; j < nodesInQueue; j++) {251Please respect copyright.ＰＥＮＡＮＡDgd8myiRjp
String node = queue.remove();251Please respect copyright.ＰＥＮＡＮＡRPZLPUIKhn
// 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)) {251Please respect copyright.ＰＥＮＡＮＡKZgiYab6yk
return steps;251Please respect copyright.ＰＥＮＡＮＡNhM6ragySY
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {251Please respect copyright.ＰＥＮＡＮＡCzTuGPdff2
for (int i = 0; i < node.length(); i++) {251Please respect copyright.ＰＥＮＡＮＡHfpEFAE57M
String neighbor = node.substring(0, i) + c + node.substring(i + 1);251Please respect copyright.ＰＥＮＡＮＡFLfoiahwH8
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {251Please respect copyright.ＰＥＮＡＮＡ8LctzROQQj
queue.add(neighbor);251Please respect copyright.ＰＥＮＡＮＡiCdgfrPYSw
seen.add(neighbor);251Please respect copyright.ＰＥＮＡＮＡlUnllINUMs
}251Please respect copyright.ＰＥＮＡＮＡwnaJcfTeVt
}251Please respect copyright.ＰＥＮＡＮＡh5VOmI0agI
}251Please respect copyright.ＰＥＮＡＮＡ0SFkmTce2S
}251Please respect copyright.ＰＥＮＡＮＡ3rZfXt9mG1
251Please respect copyright.ＰＥＮＡＮＡboJDIjraz8
steps++;251Please respect copyright.ＰＥＮＡＮＡx3BXZAbJK0
}251Please respect copyright.ＰＥＮＡＮＡD2oESAdpCq
// If we finish the BFS and did not find end, return -1.251Please respect copyright.ＰＥＮＡＮＡzLA5Ox6dqs
return -1;251Please respect copyright.ＰＥＮＡＮＡ1BeJ0Ay4sU
}251Please respect copyright.ＰＥＮＡＮＡTThryoaGK2
}
and then Add to home screen.