leetcode

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