Leetcode: Repeated DNA Sequences (hash table) (bit operation)

Problem:

https://leetcode.com/problems/repeated-dna-sequences/

-----------------------------------------------


1. Using map only:

build a frequency map using method from:

Leetcode: Substring with Concatenation of All Words (hash table)

And the result codes are:

////////////////////////////////////////////////////////

// codes 

class Solution {

public:

       vector<string> findRepeatedDnaSequences(string s) {

              vector<string> res;

              map<string, int> mapTmp;

              int n = s.size();

              if (n<10)return res;

              for (int i = 9; i<n; i++){

                     string sTmp;

                     sTmp.assign(s, i - 9, 10);

                     if (++mapTmp[sTmp] == 2) res.push_back(sTmp);

              }

              return res;

       }

};

==> memory exceeded!!!


2. How to minimize the memory used? using bit operation:

defind:

A -> 00

C -> 01

G -> 10

T -> 11

the substring with 10 characters can be transformed to a int. 

with this transformation and follow the method in 1, we have the code:

/////////////////////////////////////////////

//codes

class Solution {

private:

       int sToInt(string sTmp){

              int m = sTmp.size(), n = 0;

              for (int i = 0; i<m; i++){

                     int code = 0;

                     //coding for each character

                     switch (sTmp[i]){

                     case 'A':

                           code = 0; break;

                     case 'C':

                           code = 1; break;

                     case 'G':

                           code = 2; break;

                     case 'T':

                           code = 3; break;

                     default:;

                     }

                     n = n | code;

                     n=n << 2;

              }

              return n;

       }

public:

       vector<string> findRepeatedDnaSequences(string s) {

              vector<string> res;

              map<int, int> mapTmp;

              int n = s.size();

              if (n<10)return res;

              for (int i = 9; i<n; i++){

                     string sTmp;

                     sTmp.assign(s, i - 9, 10);

                     int k = sToInt(sTmp);//transform string to int

                     if (++mapTmp[k] == 2) res.push_back(sTmp);

              }

              return res;

       }

};