Repeated DNA Sequences
All DNA 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.
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", Return: ["AAAAACCCCC", "CCCCCAAAAA"].
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/repeated-dna-sequences ## Basic Ideas: sliding window + hashmap ## ## Complexity: Time O(n), Space O(n) class Solution(object): def findRepeatedDnaSequences(self, s): """ :type s: str :rtype: List[str] """ length = len(s) if length <= 10: return  import collections d = collections.defaultdict(lambda:0) curStr = s[0:10] d[curStr] += 1 res =  for i in range(10, length): curStr = curStr[1:] + s[i] if d[curStr] == 1: res.append(curStr) d[curStr] += 1 return res