No hashtable, bit array is used to hold occurences, 8ms C++


  • 0
    S
    class Solution {
      public:
          vector<string> findRepeatedDnaSequences(string s) {
              const int elementPerInt = 8 * sizeof(int) / 2;
              const int bucketsize = pow(2,20) / elementPerInt ;
    
              int hash[ bucketsize ];
              memset( hash, 0, bucketsize*sizeof(int) );
    
              vector<string> result;
              if(s.length()<10) return result;
    
              int k=getInt(s[0]);
              for(size_t i=1; i<s.length(); i++)
              {
                  if(i>9) k = k & 0X3FFFF;
                  k <<= 2;
                  k += getInt(s[i]);
                  if(i>=9)
                  {
                      int bucket = k / elementPerInt;
                      int placeInBucket = 2*(k%elementPerInt);
                      int mask1 = 1 << placeInBucket;
                      int mask2 = 1 << (placeInBucket+1);
    
                      if(hash[bucket] & mask1)
                      {  
                          result.push_back( s.substr( i-9,10 ) );
                          hash[bucket] -= mask1;
                          hash[bucket] += mask2;
                      }
                      else
                    	  if( (hash[bucket] & mask2) == 0) hash[bucket] += mask1;
                  }
              }
              return result;
          }
      private:
          int getInt(char c)
          {
              switch (c)
              {
                  case 'A':
                      return 0;
                  case 'C':
                      return 1;
                  case 'G':
                      return 2;
                  case 'T':
                      return 3;
              }
              return -1;
          }
      };

  • 0
    Y

    this is what i want


Log in to reply
 

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