# leetcode433. Minimum Genetic Mutation

## 题目要求

```A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3```

## 思路和代码

```    public int minMutation(String start, String end, String[] bank) {
Set<String> bankSet = new HashSet<String>();
for(String item : bank) {
}

int round = 0;
while(!queue.isEmpty()) {
int numberOfGenes = queue.size();
while(numberOfGenes-- > 0){
String tmp = queue.poll();
if(tmp.equals(end)) {
return round;
}
Iterator<String> iterator = bankSet.iterator();
while(iterator.hasNext()) {
String cur = iterator.next();
int count = 0;
for(int i = 0 ; i<start.length() ; i++) {
char c1 = tmp.charAt(i);
char c2 = cur.charAt(i);
if(c1 != c2 && ++count > 1) {
break;
}
}
if(count == 1) {
queue.offer(cur);
iterator.remove();
}
}
}
round++;
}
return -1;
}```

0 条评论

• ### docker指令学习记录

本文为学习整理和参考文章，不具有教程的功能。其次，后面将会陆续更新各种应用的容器化部署的实践，如MySQL容器化，Jenkins容器化，以供读者参考。

• ### leetcode468. Validate IP Address

校验该字符串是IPV4地址还是IPV6地址还是二者都不是。 IPV4地址通过小数点分割为4个部分，每个部分都是0～255之间的正整数，且不能包含开头的0，如01...

• ### 深入探寻JAVA8 part1：函数式编程与Lambda表达式

在很久之前粗略的看了一遍《Java8 实战》。客观的来，说这是一本写的非常好的书，它由浅入深的讲解了JAVA8的新特性以及这些新特性所解决的问题。最近重新拾起这...

• ### 轻松入门SpringBoot整合RabbitMQ

MQ全称为Message Queue, 消息队列（MQ）是一种应用程序对应用程序的通信方法。MQ是消费-生产者模型的一个典型的代表，一端往消息队列中不断写入消息...

• ### java浅拷贝和深拷贝(基础也是很重要的)

对于的github基础代码https://github.com/chywx/JavaSE

• ### 清除k8s使用underlay网络的障碍

上一篇说到在k8s里使用underlay网络有一个弊端，使用了underlay网络的pod无法访问serviceIP，这一点可能通过修改修改业务应用的chart...

• ### 基因矩阵转置文件格式（* .gmt）

gmt文件可能对于很多人来说比较陌生，但是对于使用GSEA（https://www.gsea-msigdb.org/）做过基因富集分析的人应该并不陌生。

• ### 对不起，我是音乐人：探索音乐密码学

脑洞大开，把音符映射成字母，音乐人可以把秘密隐藏在旋律中。 ? 在很多电影情节中，间谍戏和阴谋论之类的东西最能激起观众们的兴趣。我们假设一下，间谍男主角想要在一...