[RainbowSecret] summary of 2 solutions


  • 0

    Here is a really tricky solution. You need to know that the char 'A' 'C' 'G' 'T' bit representation differences.

    And by representing them with the different bits. We naturally change the string to a integer.

    class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) {
            /** cost to store the string directly is high **/
            /** we can change the string segment to a int value **/
            /** we can always use bit map to save memory if 32 bits or 64 bits is enough **/
            /** we use 3 bits to represent 'ACGT' **/
            
            unordered_map<int, bool> m;
            vector<string> result;
            for(int t=0, i=0; i<s.size(); i++){
                /** 0x3FFFFFFF : get the last 30 bits of the number **/
                /** s[i]&7 : get the last 3 bits of the number **/
                t=t<<3 & 0x3FFFFFFF | s[i]&7;
                if(m.find(t)!=m.end()){
                    if(m[t]){
                        result.push_back(s.substr(i-9, 10));
                        m[t]=false;
                    }
                }
                else{
                    m[t]=true;
                }
            }
            return result;
        }
    };
    

    But we can also defined the different representation of 'A' 'C' 'G' 'T' by ourself.

    class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) {
            /** cost to store the string directly is high **/
            /** we can change the string segment to a int value **/
            /** we can always use bit map to save memory if 32 bits or 64 bits is enough **/
            /** we use 3 bits to represent 'ACGT' **/
            
            unordered_map<int, bool> m;
            unordered_map<char, int> dict;
            dict['A']=0, dict['C']=1, dict['G']=2, dict['T']=3;
            
            vector<string> result;
            for(int t=0, i=0; i<s.size(); i++){
                /** 0x3FFFFFFF : get the last 30 bits of the number **/
                /** s[i]&7 : get the last 3 bits of the number **/
                t=((t<<2) & 0xFFFFF | dict[s[i]]);
                if(i<9) continue;
                if(m.find(t)!=m.end()){
                    if(m[t]){
                        result.push_back(s.substr(i-9, 10));
                        m[t]=false;
                    }
                }
                
                else{
                    m[t]=true;
                }
                
            }
            return result;
        }
    };

Log in to reply
 

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