Problem
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
/**
* @param {string} s
* @return {string[]}
*/
var findRepeatedDnaSequences = function(s) {
var res = [];
var map = {};
for (var i = 0; i <= s.length - 10; i++) {
var str = s.slice(i, i + 10);
var num = map[str];
if (num === -1) continue;
if (num === 1) {
map[str] = -1;
res.push(str);
continue;
}
map[str] = 1;
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).