题目描述

[EN | CN]

所有 DNA 都由一系列缩写为 ACGT 的核苷酸组成,例如 ACGAATTCCG。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列(子串)。

示例:

1
2
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC", "CCCCCAAAAA"]

解法 1:直接法

简单直接的思路,用一个 dict 来保存所有序列是否出现过 2 次。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一次;
  • 空间复杂度为 $O(n)$,保存所有情况。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        more_than_1 = {}
        for i in range(len(s) - 9):
            if s[i: i + 10] in more_than_1:
                more_than_1[s[i: i + 10]] = True
            else:
                more_than_1[s[i: i + 10]] = False
        return [k for k, v in more_than_1.items() if v]
  • 执行用时:80 ms,在所有 Python3 提交中击败了 73.01% 的用户。
  • 内存消耗:26.8 MB,在所有 Python3 提交中击败了 25.00% 的用户。