专栏首页眯眯眼猫头鹰的小树杈leetcode433. Minimum Genetic Mutation

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

假设现在有两个基因序列,并且用一个字符串数组bank来表示一个基因序列银行。已知每一步可以将当前基因序列中的一位进行改变,变成另一个已知的基因序列。问最少需要多少步可以将初始的基因序列转化为目标基因序列。如果无法转换,则返回-1。

思路和代码

其实这题是是一个典型的广度优先算法的题目。广度优先遍历通常用于寻找最短路径,将起始基因视作起点,将目标基因视作终点,而一个基因与另一个基因之间是否是相邻节点,则可以通过这两个基因之间是否只相差一个基因位进行判断。为了减少重复的遍历,每经过一个基因序列,就会将它标记为已达。代码如下:

    public int minMutation(String start, String end, String[] bank) {
        Queue<String> queue = new LinkedList<>();
        Set<String> bankSet = new HashSet<String>();
        for(String item : bank) {
            bankSet.add(item);
        }
        
        int round = 0;
        queue.add(start);
        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;
    }

对技术感兴趣的同学,欢迎加博主的微信RALE_DONG,一起学习共同进步

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

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是消费-生产者模型的一个典型的代表,一端往消息队列中不断写入消息...

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

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

    陈灬大灬海
  • Hadoop进阶之输入路径如何正则通配?

    我是攻城师
  • 黑科技 | “零损耗”温度传感器逆天了!几乎不需用电

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

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

    jeremyxu
  • 基因矩阵转置文件格式(* .gmt)

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

    生信交流平台
  • 对不起,我是音乐人:探索音乐密码学

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

    FB客服

扫码关注云+社区

领取腾讯云代金券