share my c++ solution, simple and beat 85%


  • 0
    S

    I convert the string to a unsigned integer let A=0, C=1, G=2,T=3. One linear scan will get all the numbers and count the occurrence in a hashmap. cost time 42ms

    class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) {
            //approach: the 10 char string as key cost too much memory, need some manipulation
            //if it used as a 0 1 2 3, the maximum would be 10 digits, which needs unsigned int
            //linear scan
            //actually no counter is needed, so map is not needed
            vector<string> res;
            if(s.size()<11) return res;
            unordered_map<unsigned int,int> mp; 
            unsigned int num0=str2num(s);
            mp[num0]++;
            //mp.insert(num0);
            
            const unsigned int myconst=1000000000;
            for(int i=1;i<s.size()-9;i++)
            {
                char c=s[i+9];
                int digit=0;
                switch(c)
                {
                    case 'C':digit=1;break;
                    case 'G':digit=2;break;
                    case 'T':digit=3;break;
                }
                num0=(num0%myconst)*10+digit;
                if(!mp.count(num0)) mp[num0]++;//mp.insert(num0);
                else
                {   
                    mp[num0]++;
                    if(mp[num0]==2)
                    res.push_back(s.substr(i,10)); //cannot output same string multiple times
                    
                }
            }
            return res;
            
        }
        unsigned int str2num(const string& s)
        {
            //10 chars only
            unsigned int res=0;
            for(int i=0;i<10;i++)
            {
                char c=s[i];
                int a=0;
                switch(c)
                {
                    case 'A': a=0;break;
                    case 'C': a=1;break;
                    case 'G': a=2;break;
                    case 'T': a=3;break;
                }
                res=res*10+a;
            }
            return res;
        }
    };
    

Log in to reply
 

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