leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0187.cpp (1428B)

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