重复的DNA序列（LeetCdoe）
题目
DNA序列 由一系列核苷酸组成，缩写为
'A','C','G'和'T'.。
- 例如，
"ACGAATTCCG"是一个 DNA序列 。在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串
s，返回所有在 DNA 分子中出现不止一次的 长度为10的序列(子字符串)。你可以按 任意顺序 返回答案。
解题
"""
时间复杂度: O(n)，其中 n 是字符串的长度。因为我们只需要遍历一次字符串。
空间复杂度: O(n)，因为需要存储所有长度为 10 的子串。
"""def findRepeatedDnaSequences(s):# 用于存储已经见过的子串seen = set()# 用于存储重复的子串repeated = set()# 遍历字符串，找出每个长度为10的子串for i in range(len(s) - 9):sequence = s[i:i + 10]# 如果子串已经在seen中，说明重复了，加入repeatedif sequence in seen:repeated.add(sequence)else:seen.add(sequence)# 返回重复的子串return list(repeated)# 测试
s = "ACGAATTCCGACGAATTCCG"
print(findRepeatedDnaSequences(s)) # ['ACGAATTCCG']