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 };