DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
例如，"ACGAATTCCG"?是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
示例代码1： 【哈希表】
from collections import defaultdict
class Solution(object):
def findRepeatedDnaSequences(self, s):
l = 10
dic = defaultdict(int)
ans = []
for i in range(len(s) - l + 1):
res = s[i:i + l]
dic[res] += 1
if dic[res] == 2:
ans.append(res)
return ans
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
obj = Solution()
ret = obj.findRepeatedDnaSequences(s)
print(ret)
思路分析：
- 使用哈希表统计 s?所有长度为 10的子串的出现次数，返回所有出现次数超过 10的子串。
- 代码实现时，一边遍历子串一边记录答案，为了不重复记录答案，只统计当前出现次数为 2?的子串。
复杂度分析：
- 时间复杂度：O(NL)，其中 N?是字符串s 的长度，L=10即目标子串的长度。
- 空间复杂度：O(NL)。
示例代码2：? 【滑动窗口】
class Solution(object):
def findRepeatedDnaSequences(self, s):
l = 10
if len(s) < l:
return []
ans, window = set(), set()
for i in range(len(s) - l + 1):
tmp = s[i:i + l]
if tmp not in window:
window.add(tmp)
else:
ans.add(tmp)
return list(ans)
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
s = "AAAAAAAAAAA"
obj = Solution()
ret = obj.findRepeatedDnaSequences(s)
print(ret)
