187. 重复的DNA序列

187. 重复的DNA序列

原始题目链接：https://leetcode.cn/problems/repeated-dna-sequences/

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 <= 105
s[i]==‘A’、‘C’、‘G’ or ‘T’

解题思路：

遍历字符串s，从s的开头到len(s) - 10 + 1的索引长度，跨度是10，每次统计出现的次数，当等于2次的时候符合题意，大于2次的话再记录到答案列表中会出现重复，所以判断条件等于2次即可。

代码实现：

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        from collections import defaultdict
        ans = []
        # 用一个字典记录字符串出现的次数
        # 使用int初始化
        freq_dict = defaultdict(int)

        # 遍历s，能索引的下标是从0到len(s) - 10 + 1
        for i in range(len(s) - 9):
            # 每次去i到i+10的跨度的子字符串
            sub_s = s[i: i + 10]
            # 统计次数
            freq_dict[sub_s] += 1
            # 题意要求不止一次，那么出现次数大于等于2次满足要求
            # 大于2会插入重复值，或者使用set去重也可以
            if freq_dict[sub_s] == 2:
                ans.append(sub_s)
        
        return ans

参考文献：
https://leetcode.cn/problems/repeated-dna-sequences/solution/zhong-fu-de-dnaxu-lie-by-leetcode-soluti-z8zn/