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)280Please respect copyright.ＰＥＮＡＮＡbkiRc8R3Wb
// better than use DFS as it just need to find out the shortest path.
class Solution {280Please respect copyright.ＰＥＮＡＮＡKHbc99aQEL
public int minMutation(String start, String end, String[] bank) {280Please respect copyright.ＰＥＮＡＮＡ6ke1V1EDW8
// 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.280Please respect copyright.ＰＥＮＡＮＡX5ERcWZNaZ
Queue<String> queue = new LinkedList<>();280Please respect copyright.ＰＥＮＡＮＡMg4k1pMPrA
Set<String> seen = new HashSet<>();280Please respect copyright.ＰＥＮＡＮＡAQ8Fah6jB2
queue.add(start);280Please respect copyright.ＰＥＮＡＮＡubGZLtHoeX
seen.add(start);280Please respect copyright.ＰＥＮＡＮＡ5ADO0DefQi
280Please respect copyright.ＰＥＮＡＮＡMLvF8M2HFG
int steps = 0;280Please respect copyright.ＰＥＮＡＮＡ1cJh50btlw
280Please respect copyright.ＰＥＮＡＮＡaedfpfjiNC
while (!queue.isEmpty()) {280Please respect copyright.ＰＥＮＡＮＡLlljbaYOZZ
int nodesInQueue = queue.size();280Please respect copyright.ＰＥＮＡＮＡZXMjLcjyBB
for (int j = 0; j < nodesInQueue; j++) {280Please respect copyright.ＰＥＮＡＮＡr5TOWJT8xx
String node = queue.remove();280Please respect copyright.ＰＥＮＡＮＡ6r447VBvlc
// 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)) {280Please respect copyright.ＰＥＮＡＮＡuJW09mZDKT
return steps;280Please respect copyright.ＰＥＮＡＮＡoh0YMB55BV
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {280Please respect copyright.ＰＥＮＡＮＡYBmphXUC4t
for (int i = 0; i < node.length(); i++) {280Please respect copyright.ＰＥＮＡＮＡMDig6fr1QK
String neighbor = node.substring(0, i) + c + node.substring(i + 1);280Please respect copyright.ＰＥＮＡＮＡO1Ckj23QOk
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {280Please respect copyright.ＰＥＮＡＮＡZmbnXW3gPN
queue.add(neighbor);280Please respect copyright.ＰＥＮＡＮＡpwEHt54OM9
seen.add(neighbor);280Please respect copyright.ＰＥＮＡＮＡlCvrsCiIrt
}280Please respect copyright.ＰＥＮＡＮＡJcGTvw1fKq
}280Please respect copyright.ＰＥＮＡＮＡlWqH6H2alp
}280Please respect copyright.ＰＥＮＡＮＡs74ooWJCx4
}280Please respect copyright.ＰＥＮＡＮＡ2eG8Lrf1I0
280Please respect copyright.ＰＥＮＡＮＡYoBCGvJgnQ
steps++;280Please respect copyright.ＰＥＮＡＮＡkdXw03DIkQ
}280Please respect copyright.ＰＥＮＡＮＡyeQ38ws7tQ
// If we finish the BFS and did not find end, return -1.280Please respect copyright.ＰＥＮＡＮＡlfPMmFBe9A
return -1;280Please respect copyright.ＰＥＮＡＮＡRT9v9AgMlc
}280Please respect copyright.ＰＥＮＡＮＡ3VPXmD62t5
}
