My cpp solutions


  • 0
    C

    string map:

    class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) 
        {
            vector<string> result;
            
            if(s.size() < 11) return result;
            
            std::unordered_map<string, int> substr_cnt;
            
            for(int i=0; i <= (int)s.size()-10; i++)
            {
                string substr(s.begin()+i, s.begin()+i+10);
                
                auto iter = substr_cnt.find(substr);
                
                if(iter == substr_cnt.end())
                {
                    substr_cnt[substr] = 1;
                    continue;
                }
                    
                if(iter->second == 1)
                    result.push_back(substr);
                    
                iter->second++;
            }
            
            return result;
        }
    };
    

    bitmap:

    class Solution {
    public:
        typedef unsigned int uint32;
        
        uint32 getCode(char c)
        {
            switch(c)
            {
                case 'A': return uint32(0);
                case 'C': return uint32(1);
                case 'G': return uint32(2);
                case 'T': return uint32(3);
            }
        }
        
        uint32 str2bitmap(const string &str, int start_id)
        {
            uint32 bitmap = 0;
            
            for(int i=0; i < 10; i++)
                bitmap |= ( getCode(str[start_id + i]) << (2*i) );
            
            return bitmap;
        }
        
        uint32 str2bitmap(const string &str, int start_id, int bitmap)
        {
            return (bitmap>>2) | ( getCode(str[start_id + 9]) << (2*9) );
        }
         
        vector<string> findRepeatedDnaSequences(string s) 
        {
            vector<string> result;
            
            if(s.size() < 11) return result;
            
            std::unordered_map<uint32, int> substr_cnt;
            
            uint32 bitmap = str2bitmap(s, 0);
            substr_cnt[bitmap] = 1;
            
            for(int i=1; i <= (int)s.size()-10; i++)
            {
                bitmap = str2bitmap(s, i, bitmap);
                
                auto iter = substr_cnt.find(bitmap);
                
                if(iter == substr_cnt.end())
                {
                    substr_cnt[bitmap] = 1;
                    continue;
                }
                    
                if(iter->second == 1)
                    result.push_back( s.substr(i, 10) );
                    
                iter->second++;
            }
            
            return result;
        }

Log in to reply
 

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