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)242Please respect copyright.ＰＥＮＡＮＡ7QnMaPOWLc
// better than use DFS as it just need to find out the shortest path.
class Solution {242Please respect copyright.ＰＥＮＡＮＡJTOha8miM8
public int minMutation(String start, String end, String[] bank) {242Please respect copyright.ＰＥＮＡＮＡ5yX72dYZvW
// 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.242Please respect copyright.ＰＥＮＡＮＡqPdl93wvfu
Queue<String> queue = new LinkedList<>();242Please respect copyright.ＰＥＮＡＮＡa8BqX7mjTA
Set<String> seen = new HashSet<>();242Please respect copyright.ＰＥＮＡＮＡKzOLSZKt8F
queue.add(start);242Please respect copyright.ＰＥＮＡＮＡLWG7QV2Gsd
seen.add(start);242Please respect copyright.ＰＥＮＡＮＡspFriZCDUb
242Please respect copyright.ＰＥＮＡＮＡfNcRvZm0Ta
int steps = 0;242Please respect copyright.ＰＥＮＡＮＡ0wntkrWSSJ
242Please respect copyright.ＰＥＮＡＮＡpoUsp5A1YK
while (!queue.isEmpty()) {242Please respect copyright.ＰＥＮＡＮＡIXrQK0mGWF
int nodesInQueue = queue.size();242Please respect copyright.ＰＥＮＡＮＡPm8eLJlXdx
for (int j = 0; j < nodesInQueue; j++) {242Please respect copyright.ＰＥＮＡＮＡddyAbG5ZU1
String node = queue.remove();242Please respect copyright.ＰＥＮＡＮＡhqxARvPuzM
// 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)) {242Please respect copyright.ＰＥＮＡＮＡKlGDOFrELO
return steps;242Please respect copyright.ＰＥＮＡＮＡsLRJQHjoQo
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {242Please respect copyright.ＰＥＮＡＮＡtUXte1PR6l
for (int i = 0; i < node.length(); i++) {242Please respect copyright.ＰＥＮＡＮＡOHkq2iWNDD
String neighbor = node.substring(0, i) + c + node.substring(i + 1);242Please respect copyright.ＰＥＮＡＮＡlEvu4xYE2M
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {242Please respect copyright.ＰＥＮＡＮＡGFPbjsDomu
queue.add(neighbor);242Please respect copyright.ＰＥＮＡＮＡMzvvUOyWXY
seen.add(neighbor);242Please respect copyright.ＰＥＮＡＮＡUa7s60gHSG
}242Please respect copyright.ＰＥＮＡＮＡqDIX866PA4
}242Please respect copyright.ＰＥＮＡＮＡzWQDNF27w7
}242Please respect copyright.ＰＥＮＡＮＡRY7sFAdWNZ
}242Please respect copyright.ＰＥＮＡＮＡzyB74ibNuX
242Please respect copyright.ＰＥＮＡＮＡIjweZV10OB
steps++;242Please respect copyright.ＰＥＮＡＮＡc3Hwg3vu3C
}242Please respect copyright.ＰＥＮＡＮＡLpGuPv4S0U
// If we finish the BFS and did not find end, return -1.242Please respect copyright.ＰＥＮＡＮＡJOu6vUcNX7
return -1;242Please respect copyright.ＰＥＮＡＮＡuE1gqQZ1Ys
}242Please respect copyright.ＰＥＮＡＮＡSiZKeM9sAR
}
然後按「加至主畫面」