Share my C++ solution(18ms), using a self-defined hash function


  • -1
    H
    class Solution {
        public:
        string slice(string &s,int index)
        {
            string res = "";
            for(int i = index;i < index + 10;++i)
                res += s[i];
            return res;
        }
        vector<string> findRepeatedDnaSequences(string s)
        {
            char cnt[1050000] = {0};
            vector<string> res;
            if(s.length() < 10)
                return res;
            int has = 0;
            for(int i = 0;i < 10;++i){
                switch(s[i])
                {
                case 'A':has = has * 4 + 3;break;
                case 'T':has = has * 4 + 2;break;
                case 'C':has = has * 4 + 1;break;
                case 'G':has = has * 4;
                }
            }
            cnt[has] = 1;
            cout << has << endl;
            for(int i = 1;i <= s.length() - 10;++i){
                switch(s[i - 1])
                {
                case 'A':has -= 786432;break;
                case 'T':has -= 524288;break;
                case 'C':has -= 262144;
                }
                has *= 4;
                switch(s[i + 9])
                {
                case 'A':has += 3;break;
                case 'T':has += 2;break;
                case 'C':has += 1;break;
                }
                //cout << has << endl;
                if(cnt[has] == 1)
                    res.push_back(slice(s,i));
                ++ cnt[has];
            }
            return res;
        }
    
    };

Log in to reply
 

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