Leetcode 187. Repeated DNA Sequences

https://leetcode.com/problems/repeated-dna-sequences/

Hash table is a clear solution. We can use advanced rolling hash, or just the easiest one.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {string} s
    # @return {string[]}
    def findRepeatedDnaSequences(self, s):
        length = len(s)
        if length <= 10: return []
        dict, ret = {}, []
        for i in xrange(10, length+1):
            if s[i-10 : i] in dict:
                dict[s[i-10:i]] += 1
                if s[i-10:i] not in ret:
                    ret.append(s[i-10:i])
            else:
                dict[s[i-10:i]] = 1
        return ret

Run Time: 124 ms