187. repeated DNA sequences

187. Repetitive DNA Sequence

Original title link ：https://leetcode.cn/problems/repeated-dna-sequences/

DNA Sequence It consists of a series of nucleotides , Abbreviation for ‘A’, ‘C’, ‘G’ and ‘T’..

for example ,“ACGAATTCCG” It's a DNA Sequence .
Research on DNA when , distinguish DNA The repeats in are very useful .

Given a representation DNA Sequence String s , Return all in DNA More than once in a molecule The length is 10 Sequence ( Substring ). You can press In any order Return to the answer .

Example 1：

Input ：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
Output ：[“AAAAACCCCC”,“CCCCCAAAAA”]
Example 2：

Input ：s = “AAAAAAAAAAAAA”
Output ：[“AAAAAAAAAA”]

Tips ：

0 <= s.length <= 105
s[i]==‘A’、‘C’、‘G’ or ‘T’

Their thinking ：

Traversal string s, from s From the beginning of to len(s) - 10 + 1 Index length of , The span is 10, Count the number of occurrences each time , Be equal to 2 The second time is in accordance with the meaning of the question , Greater than 2 If you record it in the answer list again, there will be a repetition , So the judgment condition is equal to 2 Next time .

Code implementation ：

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        from collections import defaultdict
        ans = []
        #  Use a dictionary to record the number of occurrences of a string 
        #  Use int initialization 
        freq_dict = defaultdict(int)

        #  Traverse s, The subscript that can be indexed is from 0 To len(s) - 10 + 1
        for i in range(len(s) - 9):
            #  Every time I go i To i+10 Substring of the span of 
            sub_s = s[i: i + 10]
            #  Count the times 
            freq_dict[sub_s] += 1
            #  The meaning of the question requires more than once , Then the number of occurrences is greater than or equal to 2 Meet the requirements for the first time 
            #  Greater than 2 Duplicate values will be inserted , Or use set Weight removal can also 
            if freq_dict[sub_s] == 2:
                ans.append(sub_s)
        
        return ans

reference ：
https://leetcode.cn/problems/repeated-dna-sequences/solution/zhong-fu-de-dnaxu-lie-by-leetcode-soluti-z8zn/