
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)261Please respect copyright.PENANAqT4yo9njVQ
// better than use DFS as it just need to find out the shortest path.
class Solution {261Please respect copyright.PENANAHLVoJVWeIJ
public int minMutation(String start, String end, String[] bank) {261Please respect copyright.PENANAcpA4RfwbRP
// 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.261Please respect copyright.PENANAVkBetluIGW
Queue<String> queue = new LinkedList<>();261Please respect copyright.PENANAhGYJc4Cylt
Set<String> seen = new HashSet<>();261Please respect copyright.PENANAVis44xBpAb
queue.add(start);261Please respect copyright.PENANAliH8JNuEKv
seen.add(start);261Please respect copyright.PENANAdOfJXHnOHn
261Please respect copyright.PENANAkcjqxF5sq5
int steps = 0;261Please respect copyright.PENANAm9VY4xpJSL
261Please respect copyright.PENANA9t5P9FcPkx
while (!queue.isEmpty()) {261Please respect copyright.PENANAPjN2S7T4ge
int nodesInQueue = queue.size();261Please respect copyright.PENANAsuBZhz2P0j
for (int j = 0; j < nodesInQueue; j++) {261Please respect copyright.PENANA4T2eGDDIeL
String node = queue.remove();261Please respect copyright.PENANAgK6h6Vvve5
// 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)) {261Please respect copyright.PENANAH9M2VWeM4k
return steps;261Please respect copyright.PENANAXc9hrZnnGn
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {261Please respect copyright.PENANA5blXcqdxR7
for (int i = 0; i < node.length(); i++) {261Please respect copyright.PENANAa4wRqu1oMJ
String neighbor = node.substring(0, i) + c + node.substring(i + 1);261Please respect copyright.PENANAwAb4tqbRBG
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {261Please respect copyright.PENANA2xOghiRUdi
queue.add(neighbor);261Please respect copyright.PENANAzUw1kDtTTR
seen.add(neighbor);261Please respect copyright.PENANAAP7Y7mN9pu
}261Please respect copyright.PENANADbNtFLlc53
}261Please respect copyright.PENANAsukfwZMhak
}261Please respect copyright.PENANA8kzvgGa6EY
}261Please respect copyright.PENANACfa6coNetP
261Please respect copyright.PENANASA2dI9zZXO
steps++;261Please respect copyright.PENANAsfdoSMWGqn
}261Please respect copyright.PENANAJoDohhmzBW
// If we finish the BFS and did not find end, return -1.261Please respect copyright.PENANA53w5Nln8Nv
return -1;261Please respect copyright.PENANATVeMOFpoAz
}261Please respect copyright.PENANA80xvdcGR8x
}