重复的DNA序列

[编程题]重复的DNA序列

热度指数：2447 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的，例如 'ACTGGGC' 。

请你实现一个函数找出所有的目标子串，目标子串的定义是，长度等于 10 ，且在 DNA 序列中出现次数超过 1 次的子串（允许两个子串有重合的部分，如下面的示例2所示）。

（注：返回的所有目标子串的顺序必须与原DNA序列的顺序一致，如下面的示例1所示）

数据范围：DNA序列长度满足 $1 \le n \le 10^5 \$ ，保证序列中只出现 'A' , 'C' , 'G' , 'T'。

示例1

输入

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出

["AAAAACCCCC","CCCCCAAAAA"]

说明

"AAAAACCCCC"和"CCCCCAAAAA"长度等于 10 且在DNA序列中分别出现了 2 次。 
不能返回["CCCCCAAAAA","AAAAACCCCC"]，因为在原DNA序列中，"AAAAACCCCC"要比"CCCCCAAAAA"先出现。

示例2

输入

"AAAAAAAAAAA"

输出

["AAAAAAAAAA"]

算法知识视频讲解

Python3

liangzhengjie

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param DNA string字符串 1
# @return string字符串一维数组
#
class Solution:
    def repeatedDNA(self , DNA: str) -> List[str]:
        # write code here
        m = {}

        res = []
        for i in range(len(DNA)-9):
            tmp_s = DNA[i:i+10]

            if tmp_s in m:
                m[tmp_s].append(i)
            else:
                m[tmp_s] = [i]

        for i in range(len(DNA)-9):
            tmp_s = DNA[i:i+10]

            if tmp_s in m:
                if m[tmp_s][0] == i and len(m[tmp_s]) > 1:
                    res.append(tmp_s)

        return res

发表于 2024-04-21 12:38:20 回复(0)