0187：重复的DNA序列（★）

Ian

2015-07-06 约 374 字预计阅读 1 分钟次阅读

力扣第 187 题

题目

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

提示：

0 <= s.length <= 10⁵
s[i]=='A'、'C'、'G' or 'T'

分析

#1

最简单的就是哈希表。

1
2
3
4


class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        ct = Counter(s[i:i+10] for i in range(len(s)-9))
        return [k for k,v in ct.items() if v>1]

51 ms

#2

当子串长度较大时，朴素哈希比较耗时，可以用滚动哈希。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        d = dict(zip('ACGT',range(4)))
        A = [d[c] for c in s]
        base,L = 4,10
        bL = base**L
        d = defaultdict(int)
        res,w = [],0
        for j,a in enumerate(A):
            w = w*base+a
            if j>=L:
                w -= A[j-L]*bL
            if j>=L-1:
                if d[w]==1:
                    res.append(s[j-L+1:j+1])
                d[w] += 1
        return res

72 ms

目录

0187：重复的DNA序列（★）

题目

分析

#1

#2

解答