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)252Please respect copyright.ＰＥＮＡＮＡLayhjTSDsP
// better than use DFS as it just need to find out the shortest path.
class Solution {252Please respect copyright.ＰＥＮＡＮＡdk54Xt1X0e
public int minMutation(String start, String end, String[] bank) {252Please respect copyright.ＰＥＮＡＮＡMOPwi6P5wv
// 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.252Please respect copyright.ＰＥＮＡＮＡ50l8l0iTgu
Queue<String> queue = new LinkedList<>();252Please respect copyright.ＰＥＮＡＮＡV0YCxeiNGj
Set<String> seen = new HashSet<>();252Please respect copyright.ＰＥＮＡＮＡUX95u8UycD
queue.add(start);252Please respect copyright.ＰＥＮＡＮＡ9I8FLAZKgt
seen.add(start);252Please respect copyright.ＰＥＮＡＮＡ1skWSRlBvI
252Please respect copyright.ＰＥＮＡＮＡohVDk1M2fn
int steps = 0;252Please respect copyright.ＰＥＮＡＮＡpiOBGniE38
252Please respect copyright.ＰＥＮＡＮＡmC2Y1Gyxzd
while (!queue.isEmpty()) {252Please respect copyright.ＰＥＮＡＮＡejg2HjsB0U
int nodesInQueue = queue.size();252Please respect copyright.ＰＥＮＡＮＡjp89eDQZKK
for (int j = 0; j < nodesInQueue; j++) {252Please respect copyright.ＰＥＮＡＮＡqRFy6NVCd3
String node = queue.remove();252Please respect copyright.ＰＥＮＡＮＡNrUUIL1Ebb
// 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)) {252Please respect copyright.ＰＥＮＡＮＡVCQEpU3z0Z
return steps;252Please respect copyright.ＰＥＮＡＮＡCfZijXkAf3
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {252Please respect copyright.ＰＥＮＡＮＡs9f2Brksuk
for (int i = 0; i < node.length(); i++) {252Please respect copyright.ＰＥＮＡＮＡlX99sAR3zs
String neighbor = node.substring(0, i) + c + node.substring(i + 1);252Please respect copyright.ＰＥＮＡＮＡ9M2N55bSsQ
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {252Please respect copyright.ＰＥＮＡＮＡPOh1YsEpqp
queue.add(neighbor);252Please respect copyright.ＰＥＮＡＮＡJOdbF3Z9sQ
seen.add(neighbor);252Please respect copyright.ＰＥＮＡＮＡvrjPzCbppj
}252Please respect copyright.ＰＥＮＡＮＡC8q5Sd2Ehy
}252Please respect copyright.ＰＥＮＡＮＡC4zZV9MqRV
}252Please respect copyright.ＰＥＮＡＮＡS3WghmiTUU
}252Please respect copyright.ＰＥＮＡＮＡL1qAdqPoYu
252Please respect copyright.ＰＥＮＡＮＡpmE74qzM44
steps++;252Please respect copyright.ＰＥＮＡＮＡjcRUyCRJGt
}252Please respect copyright.ＰＥＮＡＮＡgUyzvwojZz
// If we finish the BFS and did not find end, return -1.252Please respect copyright.ＰＥＮＡＮＡJ32lxsgtEU
return -1;252Please respect copyright.ＰＥＮＡＮＡ4fmOCJUWQg
}252Please respect copyright.ＰＥＮＡＮＡo07HEOa17y
}
