187. 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.

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

class Solution {
public:
vector findRepeatedDnaSequences(string s) {
set set_res,sequences;
int len = s.size();

    for(int i = 0; i + 9 < len; i++)
    {
        string temp = s.substr(i, 10);
        if(sequences.count(temp)) 
        {
            set_res.insert(temp);
        }
        else
        {
            sequences.insert(temp);
        }
    }
    
    return vector<string>(set_res.begin(), set_res.end());
}

};

后续优化,采用bitmap的方式减少存储。。。。。

上一篇:AtCoder Beginner Contest 187


下一篇:187-@ResultController与@Controller注解的区别?