Leetcode 187 Solution

This article provides solution to leetcode question 187 (repeated-dna-sequences)

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; } };