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)263Please respect copyright.ＰＥＮＡＮＡ52EYYtypNe
// better than use DFS as it just need to find out the shortest path.
class Solution {263Please respect copyright.ＰＥＮＡＮＡVrEsm2kEzt
public int minMutation(String start, String end, String[] bank) {263Please respect copyright.ＰＥＮＡＮＡKhS0qctCHF
// 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.263Please respect copyright.ＰＥＮＡＮＡVhsnOS6tUH
Queue<String> queue = new LinkedList<>();263Please respect copyright.ＰＥＮＡＮＡWCaiyTnrQh
Set<String> seen = new HashSet<>();263Please respect copyright.ＰＥＮＡＮＡKpADtuJrr1
queue.add(start);263Please respect copyright.ＰＥＮＡＮＡMONO1cNYwD
seen.add(start);263Please respect copyright.ＰＥＮＡＮＡPutADXpUwC
263Please respect copyright.ＰＥＮＡＮＡO8kuamWc0R
int steps = 0;263Please respect copyright.ＰＥＮＡＮＡ1PKDojOD3v
263Please respect copyright.ＰＥＮＡＮＡ5Fmh2uxPUD
while (!queue.isEmpty()) {263Please respect copyright.ＰＥＮＡＮＡwGyUlRAZeW
int nodesInQueue = queue.size();263Please respect copyright.ＰＥＮＡＮＡMhWInDI4hN
for (int j = 0; j < nodesInQueue; j++) {263Please respect copyright.ＰＥＮＡＮＡ8eprhLJhtZ
String node = queue.remove();263Please respect copyright.ＰＥＮＡＮＡ3ajKT3mqbD
// 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)) {263Please respect copyright.ＰＥＮＡＮＡmxMkTOPJA7
return steps;263Please respect copyright.ＰＥＮＡＮＡjIOP3LojOz
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {263Please respect copyright.ＰＥＮＡＮＡBtyqTxHAsJ
for (int i = 0; i < node.length(); i++) {263Please respect copyright.ＰＥＮＡＮＡeZt7T6y3Gb
String neighbor = node.substring(0, i) + c + node.substring(i + 1);263Please respect copyright.ＰＥＮＡＮＡt6uZRNzNw2
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {263Please respect copyright.ＰＥＮＡＮＡOeOnmkpjCR
queue.add(neighbor);263Please respect copyright.ＰＥＮＡＮＡdNvImgNMS8
seen.add(neighbor);263Please respect copyright.ＰＥＮＡＮＡXS7qfiIaCw
}263Please respect copyright.ＰＥＮＡＮＡ4AM0FQEwHz
}263Please respect copyright.ＰＥＮＡＮＡA2tgC32qZB
}263Please respect copyright.ＰＥＮＡＮＡmenlpsKveq
}263Please respect copyright.ＰＥＮＡＮＡyuQEtPyuUu
263Please respect copyright.ＰＥＮＡＮＡOydrc4OUNi
steps++;263Please respect copyright.ＰＥＮＡＮＡy3nXBy1bsk
}263Please respect copyright.ＰＥＮＡＮＡRPRJTK33L6
// If we finish the BFS and did not find end, return -1.263Please respect copyright.ＰＥＮＡＮＡAEeppGau0s
return -1;263Please respect copyright.ＰＥＮＡＮＡLdLOeAfMj4
}263Please respect copyright.ＰＥＮＡＮＡcN1RE5d2m4
}
