leetcodeSolution to some Leetcode problems written in C++ |
git clone git://git.dimitrijedobrota.com/leetcode.git |
Log | Files | Refs | README | LICENSE |
0187.cpp (1428B)
0 // Left to right
1 class Solution {
2 public:
3 vector<string> findRepeatedDnaSequences(string s) {
4 if (s.size() <= 10) return {};
6 unordered_map<string, int> um;
7 vector<string> res;
8 string sec = "";
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 }
18 return res;
19 }
20 };
22 // Right to left
23 class Solution {
24 public:
25 vector<string> findRepeatedDnaSequences(string s) {
26 if (s.size() <= 10) return {};
28 unordered_map<string, int> um;
29 vector<string> res;
30 string sec = "";
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 }
41 return res;
42 }
43 };
45 // Bit hacking
46 class Solution {
47 public:
48 vector<string> findRepeatedDnaSequences(string s) {
49 unordered_map<unsigned, int> um;
50 vector<string> res;
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 }
57 return res;
58 }
59 };