Leetcode 187 Solution

This article provides solution to leetcode question 187 (repeated-dna-sequences)
Categories:
Tags:
Access this page by simply typing in "lcs 187" in your browser address bar if you have bunnylol configured.

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