Repeated DNA Sequences
Total Accepted: 32259 Total Submissions: 142733 Difficulty: Medium
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"].
class Solution { public: vector<string> findRepeatedDnaSequences(string s) { int s_size = s.size(); vector<string> res; if(s_size<10){ return res; } unordered_map<string,pair<bool,bool>> umap; string str = s.substr(0,10); umap[str] = make_pair(true,false); for(int i=10;i<s_size;i++){ str.erase(str.begin()); str.push_back(s[i]); if(umap[str].first){ if(!umap[str].second){ res.push_back(str); umap[str].second = true; } }else{ umap[str] = make_pair(true,false); } } return res; } };