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)246Please respect copyright.ＰＥＮＡＮＡh33DV2IeNG
// better than use DFS as it just need to find out the shortest path.
class Solution {246Please respect copyright.ＰＥＮＡＮＡ2tXtm5txQe
public int minMutation(String start, String end, String[] bank) {246Please respect copyright.ＰＥＮＡＮＡ0Q1f7jLyyX
// 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.246Please respect copyright.ＰＥＮＡＮＡkOTTmZHukc
Queue<String> queue = new LinkedList<>();246Please respect copyright.ＰＥＮＡＮＡYfrwleVBwP
Set<String> seen = new HashSet<>();246Please respect copyright.ＰＥＮＡＮＡEgSrSMNheI
queue.add(start);246Please respect copyright.ＰＥＮＡＮＡZ8ymzP6vrs
seen.add(start);246Please respect copyright.ＰＥＮＡＮＡHiI1K5cSCr
246Please respect copyright.ＰＥＮＡＮＡ2FkkSi6SOR
int steps = 0;246Please respect copyright.ＰＥＮＡＮＡIJBRtXi9fc
246Please respect copyright.ＰＥＮＡＮＡywJjxeE1gm
while (!queue.isEmpty()) {246Please respect copyright.ＰＥＮＡＮＡzPH3dDO0li
int nodesInQueue = queue.size();246Please respect copyright.ＰＥＮＡＮＡUtl74uVhZL
for (int j = 0; j < nodesInQueue; j++) {246Please respect copyright.ＰＥＮＡＮＡz6WVdUmD5g
String node = queue.remove();246Please respect copyright.ＰＥＮＡＮＡFdy8ZWMufk
// 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)) {246Please respect copyright.ＰＥＮＡＮＡfvGoO3ACEH
return steps;246Please respect copyright.ＰＥＮＡＮＡxxuTpNOKYW
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {246Please respect copyright.ＰＥＮＡＮＡKgmI7JJfE6
for (int i = 0; i < node.length(); i++) {246Please respect copyright.ＰＥＮＡＮＡuq1dk56Wh2
String neighbor = node.substring(0, i) + c + node.substring(i + 1);246Please respect copyright.ＰＥＮＡＮＡOo4ufhny8U
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {246Please respect copyright.ＰＥＮＡＮＡgL7bCwv8UH
queue.add(neighbor);246Please respect copyright.ＰＥＮＡＮＡsoBnIGxzM8
seen.add(neighbor);246Please respect copyright.ＰＥＮＡＮＡ2AfLV9HXIP
}246Please respect copyright.ＰＥＮＡＮＡribcgkJ2gP
}246Please respect copyright.ＰＥＮＡＮＡF3lpynp9Mu
}246Please respect copyright.ＰＥＮＡＮＡftANyQIry4
}246Please respect copyright.ＰＥＮＡＮＡaPprBJG23X
246Please respect copyright.ＰＥＮＡＮＡlnTLT1K0VH
steps++;246Please respect copyright.ＰＥＮＡＮＡfCdsoXGibI
}246Please respect copyright.ＰＥＮＡＮＡ7gDYGimVC0
// If we finish the BFS and did not find end, return -1.246Please respect copyright.ＰＥＮＡＮＡ2RVdUewigY
return -1;246Please respect copyright.ＰＥＮＡＮＡtHFEYCkBMa
}246Please respect copyright.ＰＥＮＡＮＡLtFhz6Fzb3
}
