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)270Please respect copyright.ＰＥＮＡＮＡFsUbPDrlTf
// better than use DFS as it just need to find out the shortest path.
class Solution {270Please respect copyright.ＰＥＮＡＮＡCclV2EA15E
public int minMutation(String start, String end, String[] bank) {270Please respect copyright.ＰＥＮＡＮＡTMZUNsn9X9
// 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.270Please respect copyright.ＰＥＮＡＮＡnw9BYrEWbs
Queue<String> queue = new LinkedList<>();270Please respect copyright.ＰＥＮＡＮＡPun7iJaUvC
Set<String> seen = new HashSet<>();270Please respect copyright.ＰＥＮＡＮＡ6G0GVK89tP
queue.add(start);270Please respect copyright.ＰＥＮＡＮＡLFhUTYy2la
seen.add(start);270Please respect copyright.ＰＥＮＡＮＡiV80VdgIhI
270Please respect copyright.ＰＥＮＡＮＡy8v6hgkMpF
int steps = 0;270Please respect copyright.ＰＥＮＡＮＡGxH1vlNBCy
270Please respect copyright.ＰＥＮＡＮＡv2PUQEeAz5
while (!queue.isEmpty()) {270Please respect copyright.ＰＥＮＡＮＡtRKp9UZpaz
int nodesInQueue = queue.size();270Please respect copyright.ＰＥＮＡＮＡv0IWtJhL7d
for (int j = 0; j < nodesInQueue; j++) {270Please respect copyright.ＰＥＮＡＮＡHZDZFJs1jn
String node = queue.remove();270Please respect copyright.ＰＥＮＡＮＡoydV4dVMLh
// 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)) {270Please respect copyright.ＰＥＮＡＮＡAnYtFJ5ZPX
return steps;270Please respect copyright.ＰＥＮＡＮＡTExQqIG8t0
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {270Please respect copyright.ＰＥＮＡＮＡrdg5JaR1Y1
for (int i = 0; i < node.length(); i++) {270Please respect copyright.ＰＥＮＡＮＡDDbDb0PSLk
String neighbor = node.substring(0, i) + c + node.substring(i + 1);270Please respect copyright.ＰＥＮＡＮＡwwAvgGk2R0
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {270Please respect copyright.ＰＥＮＡＮＡw5fKiDKpU5
queue.add(neighbor);270Please respect copyright.ＰＥＮＡＮＡn39HEWVSBN
seen.add(neighbor);270Please respect copyright.ＰＥＮＡＮＡxYjKLoclBj
}270Please respect copyright.ＰＥＮＡＮＡ1ADA6YFFcM
}270Please respect copyright.ＰＥＮＡＮＡlOWHxuIEtf
}270Please respect copyright.ＰＥＮＡＮＡFEo2R9Mxqq
}270Please respect copyright.ＰＥＮＡＮＡpL0BG47rca
270Please respect copyright.ＰＥＮＡＮＡhrxp2od8JF
steps++;270Please respect copyright.ＰＥＮＡＮＡzNeDdLgtUP
}270Please respect copyright.ＰＥＮＡＮＡs9IxH4uq8h
// If we finish the BFS and did not find end, return -1.270Please respect copyright.ＰＥＮＡＮＡiwVdainl99
return -1;270Please respect copyright.ＰＥＮＡＮＡgDA906HS27
}270Please respect copyright.ＰＥＮＡＮＡAZzyaCiO1W
}
然後按「加至主畫面」