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)290Please respect copyright.ＰＥＮＡＮＡpBUJ0NIPqj
// better than use DFS as it just need to find out the shortest path.
class Solution {290Please respect copyright.ＰＥＮＡＮＡIaRFm0ydZU
public int minMutation(String start, String end, String[] bank) {290Please respect copyright.ＰＥＮＡＮＡtwN8l2HqCw
// 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.290Please respect copyright.ＰＥＮＡＮＡ8HlWYALjg2
Queue<String> queue = new LinkedList<>();290Please respect copyright.ＰＥＮＡＮＡDMx5eKje5j
Set<String> seen = new HashSet<>();290Please respect copyright.ＰＥＮＡＮＡ8gzK6m0VKN
queue.add(start);290Please respect copyright.ＰＥＮＡＮＡ0tdkbtahSD
seen.add(start);290Please respect copyright.ＰＥＮＡＮＡzF78Sbr2Kv
290Please respect copyright.ＰＥＮＡＮＡ0jwAf3VL7n
int steps = 0;290Please respect copyright.ＰＥＮＡＮＡSapz8ogUPJ
290Please respect copyright.ＰＥＮＡＮＡtqksJ9jszO
while (!queue.isEmpty()) {290Please respect copyright.ＰＥＮＡＮＡ6rS21Lt43M
int nodesInQueue = queue.size();290Please respect copyright.ＰＥＮＡＮＡ0d455o3iG7
for (int j = 0; j < nodesInQueue; j++) {290Please respect copyright.ＰＥＮＡＮＡpP2R3V2fO8
String node = queue.remove();290Please respect copyright.ＰＥＮＡＮＡmxHlhjCAhT
// 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)) {290Please respect copyright.ＰＥＮＡＮＡJV7efw8P8c
return steps;290Please respect copyright.ＰＥＮＡＮＡ4cswstrE6n
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {290Please respect copyright.ＰＥＮＡＮＡGRO45QFG5h
for (int i = 0; i < node.length(); i++) {290Please respect copyright.ＰＥＮＡＮＡXXAJBtMAdI
String neighbor = node.substring(0, i) + c + node.substring(i + 1);290Please respect copyright.ＰＥＮＡＮＡ6ORqGL9pZR
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {290Please respect copyright.ＰＥＮＡＮＡcBAounvDSu
queue.add(neighbor);290Please respect copyright.ＰＥＮＡＮＡHTukAwjeSB
seen.add(neighbor);290Please respect copyright.ＰＥＮＡＮＡsrNZjTLfft
}290Please respect copyright.ＰＥＮＡＮＡimqy4jli7U
}290Please respect copyright.ＰＥＮＡＮＡoyquXuH5JC
}290Please respect copyright.ＰＥＮＡＮＡiSiC66pBQd
}290Please respect copyright.ＰＥＮＡＮＡrtEUOMUpr1
290Please respect copyright.ＰＥＮＡＮＡm9nK79fOiu
steps++;290Please respect copyright.ＰＥＮＡＮＡRkxMTbzLs7
}290Please respect copyright.ＰＥＮＡＮＡXtXtVAnMai
// If we finish the BFS and did not find end, return -1.290Please respect copyright.ＰＥＮＡＮＡ7khm7nqrnR
return -1;290Please respect copyright.ＰＥＮＡＮＡMrHMt76JlG
}290Please respect copyright.ＰＥＮＡＮＡsSzVW7KqcE
}
