这道题可以看成一个24叉树。
因为基因序列长度固定为8，且每个位置的字母固定是AGCT，可以选择改变的只有3个字母，所以一次最多24种情况。
然后检查变化后的结果是否存在bank中（使用hashSet来存储），同时设置一个visited集合来检查是否访问过。
class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
if (startGene.equals(endGene))
return 0;
char[] keys = {
'A', 'G', 'C', 'T' };
Set<String> cnt = new HashSet<>();
Set<String> visited = new HashSet<>();
for (String str : bank) {
cnt.add(str);
}
if (!cnt.contains(endGene))
return -1;
Queue<String> q = new ArrayDeque<>();
q.offer(startGene);
visited.add(startGene);
int step = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
String curr = q.poll();
for (int u = 0; u < 8; ++u) {
for (int v = 0; v < 4; ++v) {
if (keys[v] != curr.charAt(u)) {
StringBuffer sb = new StringBuffer(curr);
sb.setCharAt(u, keys[v]);
String next = sb.toString();
if (!visited.contains(next) && cnt.contains(next)) {
if (next.equals(endGene))
return step;
visited.add(next);
q.offer(next);
}
}
}
}
}
++step;
}
return -1;
}
}
拓展：Queue使用ArrayList和LinkedList进行声明的区别
在Java中，Queue可以使用ArrayList和LinkedList进行声明。这两种数据结构在实现Queue时有一些区别。
使用ArrayList声明Queue的区别：
底层数据结构：
- ArrayList基于动态数组实现，它可以动态增长和缩小。
- 插入和删除元素可能涉及重新分配内存和数据复制。
适用场景：
- 当需要随机访问队列中的元素时，ArrayList是更好的选择，因为它支持通过索引直接访问元素。
- 如果需要频繁对队列进行随机访问、而且对队列的修改操作相对较少时，可以考虑使用ArrayList实现Queue。
使用LinkedList声明Queue的区别：
底层数据结构：
- LinkedList基于双向链表实现，每个元素都指向前一个和后一个元素。
- 插入和删除元素的时间复杂度为O(1)，因为只需要调整指针而不需要大量数据的搬移。
适用场景：
- 当需要频繁对队列进行插入、删除操作时，LinkedList是更好的选择，因为它的插入和删除操作效率更高。
- 如果队列的操作主要是在两端进行（即头部和尾部），比如经常需要在队列头部和尾部进行插入、删除操作，可以考虑使用LinkedList实现Queue。
综合考虑：
- 如果对队列中的元素进行频繁的随机访问，可以选择ArrayList实现Queue。
- 如果对队列中的元素进行频繁的插入、删除操作，可以选择LinkedList实现Queue。
在实际应用中，需要根据具体的场景和需求来选择合适的数据结构来实现Queue。
