187. Repeated DNA Sequences

Posted on | In | Visitors:

Repeated DNA Sequences

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
29
30
31
32
33
34
35
#! /usr/bin/python

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
#        print s
        l = len(s)
#        print l
        dict = {}        
        for i in range(l-9):
#            print i        
            substr = s[i:i+10]
            if dict.has_key(substr):
                dict[substr] = dict[substr] + 1
            else:
                dict[substr] = 1

#        print dict
        
        list = []
        for keys in dict.keys():
#            print keys
            if dict[keys] > 1:
                list.append(keys)

        print list
        return list

if __name__ == "__main__":
    S = Solution()
    s = raw_input()
    S.findRepeatedDnaSequences(s)