Leetcode 187 Repeated DNA sequence (2022.07.06)

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 <= 10⁵
s[i]==‘A’、‘C’、‘G’ or ‘T’

source ： Power button （LeetCode）

Method 1 ： Hashtable

C++ Submission ：

class Solution {
    
    const int L = 10;
public:
    vector<string> findRepeatedDnaSequences(string s) {
    
        vector<string> ans;
        unordered_map<string, int> cnt;
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
    
            string sub = s.substr(i, L);
            if (++cnt[sub] == 2) {
    
                ans.push_back(sub);
            }
        }
        return ans;
    }
};