LeetCode187—Repeated DNA Sequences-蒲公英云

LeetCode187—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.

For example,

Given s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”,

Return:
[“AAAAACCCCC”, “CCCCCAAAAA”].

分析

重复出现的子串，长度为10。
用一个hash来保存，最后结果去重即可。

class Solution{ 
    public:
    vector<string> findRepeatedDnaSequences(string s)
    { 
        vector<string>result;
        unordered_set<string>visited;
        for(int i=0;i+10<=s.size();++i)
        {
            string tmp(s.begin()+i,s.begin()+i+10);
            if(visited.end()==visited.find(tmp))
            {
                visited.insert(tmp);
            }
            else
                result.push_back(tmp);
        }
        //去重
        result.erase(unique(result.begin(),result.end()),result.end());
        //打印
       // ostream_iterator<string> out_it(cout,"\n");
       // copy(result.begin(),result.end(),out_it);
        return result;
    } 
};