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)92Please respect copyright.PENANA468bP9YlWs
// better than use DFS as it just need to find out the shortest path.
class Solution {92Please respect copyright.PENANAraHRfPgqmT
public int minMutation(String start, String end, String[] bank) {92Please respect copyright.PENANAvlzZ5hkWTz
// 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.92Please respect copyright.PENANAAGDhlRWW6h
Queue<String> queue = new LinkedList<>();92Please respect copyright.PENANAuqG0MkVwoA
Set<String> seen = new HashSet<>();92Please respect copyright.PENANA1uBaKL1Wk1
queue.add(start);92Please respect copyright.PENANAjELj9X3ObJ
seen.add(start);92Please respect copyright.PENANAZ3C9s4RY8n
92Please respect copyright.PENANAIZKYQHTD6u
int steps = 0;92Please respect copyright.PENANAnXzRqFvdMr
92Please respect copyright.PENANAbzPlhhO4LS
while (!queue.isEmpty()) {92Please respect copyright.PENANA9X7Ve97wJP
int nodesInQueue = queue.size();92Please respect copyright.PENANAMUBj0ZV0dT
for (int j = 0; j < nodesInQueue; j++) {92Please respect copyright.PENANADnLxYxOftA
String node = queue.remove();92Please respect copyright.PENANArBSbJedewl
// 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)) {92Please respect copyright.PENANAERjRqvNDCi
return steps;92Please respect copyright.PENANADx1ZEk5G4P
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {92Please respect copyright.PENANAq5oRCmghcy
for (int i = 0; i < node.length(); i++) {92Please respect copyright.PENANAN5E9GYqprK
String neighbor = node.substring(0, i) + c + node.substring(i + 1);92Please respect copyright.PENANAAX9qulpkYg
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {92Please respect copyright.PENANAuPld5yp02w
queue.add(neighbor);92Please respect copyright.PENANApMmht4qdu0
seen.add(neighbor);92Please respect copyright.PENANAIMC5Htu1KB
}92Please respect copyright.PENANAR6vXovxF3r
}92Please respect copyright.PENANAxhoB8PBc4t
}92Please respect copyright.PENANA1qy5gsgjLJ
}92Please respect copyright.PENANAqvd73tjXWT
92Please respect copyright.PENANAtrrd59S23K
steps++;92Please respect copyright.PENANAOx1NVaz3YV
}92Please respect copyright.PENANA3phs7YH1k3
// If we finish the BFS and did not find end, return -1.92Please respect copyright.PENANAVGABA0I6im
return -1;92Please respect copyright.PENANAhnAtcYjNrv
}92Please respect copyright.PENANA5YdD5cnDtO
}