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)204Please respect copyright.ＰＥＮＡＮＡwoxLTC7qL5
// better than use DFS as it just need to find out the shortest path.
class Solution {204Please respect copyright.ＰＥＮＡＮＡAIVOqTbLgS
public int minMutation(String start, String end, String[] bank) {204Please respect copyright.ＰＥＮＡＮＡqyRUfiP2PB
// 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.204Please respect copyright.ＰＥＮＡＮＡ9jEW7PkWPJ
Queue<String> queue = new LinkedList<>();204Please respect copyright.ＰＥＮＡＮＡD0Inyj4dls
Set<String> seen = new HashSet<>();204Please respect copyright.ＰＥＮＡＮＡyLVAfSbQga
queue.add(start);204Please respect copyright.ＰＥＮＡＮＡkTeQXoP8BY
seen.add(start);204Please respect copyright.ＰＥＮＡＮＡ7GdzlvMvV4
204Please respect copyright.ＰＥＮＡＮＡiKlkUuauPG
int steps = 0;204Please respect copyright.ＰＥＮＡＮＡl9RDWu7FqJ
204Please respect copyright.ＰＥＮＡＮＡ0Vxqg8G0Uj
while (!queue.isEmpty()) {204Please respect copyright.ＰＥＮＡＮＡYSrDe3123q
int nodesInQueue = queue.size();204Please respect copyright.ＰＥＮＡＮＡJisevmBnj7
for (int j = 0; j < nodesInQueue; j++) {204Please respect copyright.ＰＥＮＡＮＡmJkPLhfRt1
String node = queue.remove();204Please respect copyright.ＰＥＮＡＮＡrpLpwyk2jE
// 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)) {204Please respect copyright.ＰＥＮＡＮＡoVkpqj6Fb5
return steps;204Please respect copyright.ＰＥＮＡＮＡqesaY2037a
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {204Please respect copyright.ＰＥＮＡＮＡaeFsQqRSJl
for (int i = 0; i < node.length(); i++) {204Please respect copyright.ＰＥＮＡＮＡhnGtngKICX
String neighbor = node.substring(0, i) + c + node.substring(i + 1);204Please respect copyright.ＰＥＮＡＮＡGvM9k5mvg8
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {204Please respect copyright.ＰＥＮＡＮＡ2L1hN9VViy
queue.add(neighbor);204Please respect copyright.ＰＥＮＡＮＡT6NNBDVWhD
seen.add(neighbor);204Please respect copyright.ＰＥＮＡＮＡ5wt6ObLAeD
}204Please respect copyright.ＰＥＮＡＮＡme1O8aVJIr
}204Please respect copyright.ＰＥＮＡＮＡMqC7zK989f
}204Please respect copyright.ＰＥＮＡＮＡzzlTeRpv1M
}204Please respect copyright.ＰＥＮＡＮＡlCxP4PJ7Ht
204Please respect copyright.ＰＥＮＡＮＡKEK6l2Mpq1
steps++;204Please respect copyright.ＰＥＮＡＮＡ5xV2TCHS8n
}204Please respect copyright.ＰＥＮＡＮＡP8JEb05CCe
// If we finish the BFS and did not find end, return -1.204Please respect copyright.ＰＥＮＡＮＡ3g5I9utfKJ
return -1;204Please respect copyright.ＰＥＮＡＮＡUIqE1A6PUJ
}204Please respect copyright.ＰＥＮＡＮＡFxp8wPjYgr
}
