LeetCode – Refresh – Repeated DNA Sequences

Follow the hint from https://leetcode.com/discuss/24478/i-did-it-in-10-lines-of-c

1. The last three digits of binary format will be :

A   001

C   011

G   111

T　100

So as 10 chars need 3 * 10 bits to record the status. We choose 0x3FFFFFF, still less than 32 bits.

9 chars: 0x1FFFFFFF

8 chars:    0xFFFFFF

7              0x1FFFFF

6              0x3FFFF

5              0x7FFF

4　　        0xFFF

3              0x1FF

2              0x3F

1              0x7

Code:

 1 class Solution {
 2 public:
 3     vector<string> findRepeatedDnaSequences(string s) {
 4         vector<string> result;
 5         unordered_map<int, int> record;
 6         int current = 0, len = s.size();
 7         for (int i = 0; i < len; i++) {
 8             if (record[current = (current << 3 & 0x3FFFFFFF | s[i] & 7)]++ == 1) {
 9                 result.push_back(s.substr(i-9, 10));
10             }
11         }
12         return result;
13     }
14 };

LeetCode – Refresh – Repeated DNA Sequences

原文：http://www.cnblogs.com/shuashuashua/p/4356877.html