Leetcode 187 Solution
This article provides solution to leetcode question 187 (repeated-dna-sequences)
Access this page by simply typing in "lcs 187" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
https://leetcode.com/problems/repeated-dna-sequences
Solution
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<int, int> a;
int curr = 0;
vector<string> res;
for (int i = 0; i < s.size(); i++)
{
int x = 0;
if (s[i] == 'A')
x = 0;
else if (s[i] == 'C')
x = 1;
else if (s[i] == 'G')
x = 2;
else if (s[i] == 'T')
x = 3;
curr = (curr * 4 + x) % 1048576;
if (i >= 9)
a[curr]++;
}
for (int i = 0; i < s.size(); i++)
{
int x = 0;
if (s[i] == 'A')
x = 0;
else if (s[i] == 'C')
x = 1;
else if (s[i] == 'G')
x = 2;
else if (s[i] == 'T')
x = 3;
curr = (curr * 4 + x) % 1048576;
if (i >= 9 && a[curr] > 1)
{
res.push_back(s.substr(i - 9, 10));
a[curr] = 0;
}
}
return res;
}
};