187. Repeated DNA Sequences
The DNA sequence is composed of a series of nucleotides abbreviated as 'A'
, 'C'
, 'G'
, and 'T'
.
- For example,
"ACGAATTCCG"
is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s
that represents a DNA sequence, return all the 10
-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"]
Example 2:
Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]
Constraints:
1 <= s.length <= 105
s[i]
is either'A'
,'C'
,'G'
, or'T'
.
solution:
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int size = s.length();
unordered_map<string, int>umap;
vector<string>ans;
if(size <= 10)
return ans;
for(int i =0 ; i <= size-10; i++ )
{
string t = s.substr(i , 10);
umap[t]++;
}
for(int i =0 ; i < size-10; i++ )
{
string t = s.substr(i , 10);
if(umap[t] > 1)
{
ans.push_back(t);
umap[t] =0;
}
}
return ans;
}
};
Comments
Post a Comment