leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0187.cpp (1428B)

      1 // Left to right
      2 class Solution {
      3   public:
      4     vector<string> findRepeatedDnaSequences(string s) {
      5         if (s.size() <= 10) return {};
      6 
      7         unordered_map<string, int> um;
      8         vector<string> res;
      9         string sec = "";
     10 
     11         for (int i = 0; i < 10; i++)
     12             sec += s[i];
     13         um[sec]++;
     14         for (int i = 10; i < s.size(); i++) {
     15             sec = sec.substr(1) + s[i];
     16             if (um[sec]++ == 1) res.push_back(sec);
     17         }
     18 
     19         return res;
     20     }
     21 };
     22 
     23 // Right to left
     24 class Solution {
     25   public:
     26     vector<string> findRepeatedDnaSequences(string s) {
     27         if (s.size() <= 10) return {};
     28 
     29         unordered_map<string, int> um;
     30         vector<string> res;
     31         string sec = "";
     32 
     33         for (int i = s.size() - 1; i >= s.size() - 10; i--)
     34             sec = s[i] + sec;
     35         um[sec]++;
     36         for (int i = s.size() - 10 - 1; i >= 0; i--) {
     37             sec.pop_back();
     38             sec = s[i] + sec;
     39             if (um[sec]++ == 1) res.push_back(sec);
     40         }
     41 
     42         return res;
     43     }
     44 };
     45 
     46 // Bit hacking
     47 class Solution {
     48   public:
     49     vector<string> findRepeatedDnaSequences(string s) {
     50         unordered_map<unsigned, int> um;
     51         vector<string> res;
     52 
     53         for (unsigned i = 0, sec = 0; i < s.size(); i++) {
     54             sec = sec << 3 & 0x3FFFFFFF | s[i] & 7;
     55             if (um[sec]++ == 1) res.push_back(s.substr(i - 9, 10));
     56         }
     57 
     58         return res;
     59     }
     60 };