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)93Please respect copyright.ＰＥＮＡＮＡTIlQHT6UOp
// better than use DFS as it just need to find out the shortest path.
class Solution {93Please respect copyright.ＰＥＮＡＮＡhflxn49Uv4
public int minMutation(String start, String end, String[] bank) {93Please respect copyright.ＰＥＮＡＮＡN7ePe5kwMl
// 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.93Please respect copyright.ＰＥＮＡＮＡZOgJrPtRNY
Queue<String> queue = new LinkedList<>();93Please respect copyright.ＰＥＮＡＮＡN0rNTDoeRH
Set<String> seen = new HashSet<>();93Please respect copyright.ＰＥＮＡＮＡgqb2oMk7YQ
queue.add(start);93Please respect copyright.ＰＥＮＡＮＡOmZNGDm74u
seen.add(start);93Please respect copyright.ＰＥＮＡＮＡkf0Mx31pTz
93Please respect copyright.ＰＥＮＡＮＡhMvva3Vi0m
int steps = 0;93Please respect copyright.ＰＥＮＡＮＡJtPsf13Elm
93Please respect copyright.ＰＥＮＡＮＡ9ccItpt1no
while (!queue.isEmpty()) {93Please respect copyright.ＰＥＮＡＮＡ8gcVbWBRR6
int nodesInQueue = queue.size();93Please respect copyright.ＰＥＮＡＮＡ4fto52olyY
for (int j = 0; j < nodesInQueue; j++) {93Please respect copyright.ＰＥＮＡＮＡ1Z4hszwhOn
String node = queue.remove();93Please respect copyright.ＰＥＮＡＮＡIA5MQckhLJ
// 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)) {93Please respect copyright.ＰＥＮＡＮＡuvRr5foF6a
return steps;93Please respect copyright.ＰＥＮＡＮＡuqpvfrXfmt
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {93Please respect copyright.ＰＥＮＡＮＡmNGXqDVnZc
for (int i = 0; i < node.length(); i++) {93Please respect copyright.ＰＥＮＡＮＡuZ9tSqobCh
String neighbor = node.substring(0, i) + c + node.substring(i + 1);93Please respect copyright.ＰＥＮＡＮＡf3THi4PFF8
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {93Please respect copyright.ＰＥＮＡＮＡfkIeiJqokj
queue.add(neighbor);93Please respect copyright.ＰＥＮＡＮＡKLibURHA2l
seen.add(neighbor);93Please respect copyright.ＰＥＮＡＮＡPK2ebFI3uE
}93Please respect copyright.ＰＥＮＡＮＡwv2exqO3va
}93Please respect copyright.ＰＥＮＡＮＡzp9QK9cIiB
}93Please respect copyright.ＰＥＮＡＮＡAfZer6LfRa
}93Please respect copyright.ＰＥＮＡＮＡO04XrdY7YU
93Please respect copyright.ＰＥＮＡＮＡTH1lZRc1aV
steps++;93Please respect copyright.ＰＥＮＡＮＡcFqc9j4O0x
}93Please respect copyright.ＰＥＮＡＮＡvV838kQOCR
// If we finish the BFS and did not find end, return -1.93Please respect copyright.ＰＥＮＡＮＡR9H0gLpcg7
return -1;93Please respect copyright.ＰＥＮＡＮＡURyzGd6Git
}93Please respect copyright.ＰＥＮＡＮＡdu2EL7Ygcu
}
and then Add to home screen.