aboutsummaryrefslogtreecommitdiff
path: root/repeated_dna_sequences.py
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"))