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)232Please respect copyright.ＰＥＮＡＮＡiLLkZS2riX
// better than use DFS as it just need to find out the shortest path.
class Solution {232Please respect copyright.ＰＥＮＡＮＡ6V3jGLwjnS
public int minMutation(String start, String end, String[] bank) {232Please respect copyright.ＰＥＮＡＮＡ5IkbiLV3vR
// 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.232Please respect copyright.ＰＥＮＡＮＡ3K3N2lTh29
Queue<String> queue = new LinkedList<>();232Please respect copyright.ＰＥＮＡＮＡ1opdPW3rkC
Set<String> seen = new HashSet<>();232Please respect copyright.ＰＥＮＡＮＡT7EeIinalI
queue.add(start);232Please respect copyright.ＰＥＮＡＮＡoq50R4CdLu
seen.add(start);232Please respect copyright.ＰＥＮＡＮＡVBaQEJmVSA
232Please respect copyright.ＰＥＮＡＮＡDIftucUUTH
int steps = 0;232Please respect copyright.ＰＥＮＡＮＡNkWoOvTACb
232Please respect copyright.ＰＥＮＡＮＡIshWqG8PvP
while (!queue.isEmpty()) {232Please respect copyright.ＰＥＮＡＮＡlVDDWUOGZl
int nodesInQueue = queue.size();232Please respect copyright.ＰＥＮＡＮＡhfcONJYmQb
for (int j = 0; j < nodesInQueue; j++) {232Please respect copyright.ＰＥＮＡＮＡNobIcBe9og
String node = queue.remove();232Please respect copyright.ＰＥＮＡＮＡc00Hd2qZMY
// 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)) {232Please respect copyright.ＰＥＮＡＮＡj9Qi4rbY3J
return steps;232Please respect copyright.ＰＥＮＡＮＡ8MgcO8KPdR
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {232Please respect copyright.ＰＥＮＡＮＡe7OYNv8WAV
for (int i = 0; i < node.length(); i++) {232Please respect copyright.ＰＥＮＡＮＡohv2o15wIQ
String neighbor = node.substring(0, i) + c + node.substring(i + 1);232Please respect copyright.ＰＥＮＡＮＡNByFnycISj
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {232Please respect copyright.ＰＥＮＡＮＡ8gTmsmW6Y3
queue.add(neighbor);232Please respect copyright.ＰＥＮＡＮＡr96e8N53zg
seen.add(neighbor);232Please respect copyright.ＰＥＮＡＮＡu8mXozQZ0W
}232Please respect copyright.ＰＥＮＡＮＡUC2reoOOCh
}232Please respect copyright.ＰＥＮＡＮＡ6Gr2iZvKN7
}232Please respect copyright.ＰＥＮＡＮＡAbSQokqxHv
}232Please respect copyright.ＰＥＮＡＮＡbfDj1KMrWa
232Please respect copyright.ＰＥＮＡＮＡV5us3UmoHg
steps++;232Please respect copyright.ＰＥＮＡＮＡXQhSp6wha1
}232Please respect copyright.ＰＥＮＡＮＡibIQ6FSZ7f
// If we finish the BFS and did not find end, return -1.232Please respect copyright.ＰＥＮＡＮＡu1fimtx4iL
return -1;232Please respect copyright.ＰＥＮＡＮＡiP4HsRSf2v
}232Please respect copyright.ＰＥＮＡＮＡeZvFqfxCfJ
}
