Share my C++ solution, 12ms


  • 0
    R
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> sout;
        if(s.size() <= 10) return sout;
        char a[262143] = {'\0'};
        char t[262143] = {'\0'};
        char g[262143] = {'\0'};
        char c[262143] = {'\0'};
        int m = 0;
        for(int i=1; i<10; i++)
        {
            m = m<<2;
            if(s[i] == 'A') m = m | 0;
            else if(s[i] == 'T') m = m | 1;
            else if(s[i] == 'G') m = m | 2;
            else m = m | 3;
        }
        if(s[0] == 'A') a[m] = 't';
        else if(s[0] == 'T') t[m] = 't';
        else if(s[0] == 'G') g[m] = 't';
        else c[m] = 't';
        int n = s.size() - 10;
        int mask = 262143;
        for(int i=1; i<=n; i++)
        {
            m = m<<2;
            m = m & mask;
            if(s[i+9] == 'A') m = m | 0;
            else if(s[i+9] == 'T') m = m | 1;
            else if(s[i+9] == 'G') m = m | 2;
            else m = m | 3;
            if(s[i] == 'A')
            {
                if(a[m] == '\0') a[m] = 't';
                else if(a[m] == 't')
                {
                    sout.push_back(s.substr(i,10));
                    a[m] = 'f';
                }
            }
            else if(s[i] == 'T')
            {
                if(t[m] == '\0') t[m] = 't';
                else if(t[m] == 't')
                {
                    sout.push_back(s.substr(i,10));
                    t[m] = 'f';
                }
            }
            else if(s[i] == 'G')
            {
                if(g[m] == '\0') g[m] = 't';
                else if(g[m] == 't')
                {
                    sout.push_back(s.substr(i,10));
                    g[m] = 'f';
                }
            }
            else
            {
                if(c[m] == '\0') c[m] = 't';
                else if(c[m] == 't')
                {
                    sout.push_back(s.substr(i,10));
                    c[m] = 'f';
                }
            }
        }
        return sout;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.