blob: 175fd9abf5f5b189c842d7da9622b1b01c1f3bdd (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
# 187. Repeated DNA Sequences
from collections import defaultdict
"""
the dna sequence is composed of a series of nucleotides abbreviated as A, C,
G, and T. when studying dna it is useful to identify repeated sequences
within the dna. given a string 's' that represents a dna sequence, return all
the 10 letter long sequences (substrings) that occur more than once in a dna
molecule. you may return the answer in any order
"""
class Solution(object):
def findRepeatedDnaSequences(self, s):
"""
:type s: str
:rtype: List[str]
"""
seq = defaultdict(int)
for i in range(len(s)):
seq[s[i : i + 10]] += 1
return [key for key, val in seq.iteritems() if val > 1]
if __name__ == "__main__":
obj = Solution()
print(obj.findRepeatedDnaSequences(s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"))
print(obj.findRepeatedDnaSequences(s="AAAAAAAAAAAAA"))
|