题目地址: https://leetcode.com/problems/repeated-dna-sequences/description/
题目描述：
AllDNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
题目大意
在一个字符串中找出连续的十个字符，这十个字符不止在一个地方出现过。
解题方法
遍历+set。
做法简单了，需要一个长度是10的字符串切片，从头到尾把字符遍历一遍，然后不停的判断以这个位置开头的10个字符构成的字符串是否看到过，如果看到过就放到另外一个set里。为什么不直接放入list返回呢？因为一个字符串可能会重复多次，为了防止重复添加到结果里，必须set一下。
时间复杂度是O(N)，空间复杂度是O(N)。
class Solution(object):
def findRepeatedDnaSequences(self, s):
"""
:type s: str
:rtype: List[str]
"""
seen = set()
repeated = set()
N = len(s)
for i in range(N):
cur = s[i : i+ 10]
if cur in seen:
repeated.add(cur)
else:
seen.add(cur)
return list(repeated)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
参考资料：
https://leetcode.com/problems/repeated-dna-sequences/discuss/53855/7-lines-simple-Java-O(n)
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发