【Leetcode】【Medium】Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

思考：

1、这是一道非常典型的求重复字符子串的问题，涉及到记录和查找，使用hash表最省时间，hash表需要key值取数字，自然考虑到将字符串转为ASCII码；

2、由于字母只有4种可能，那么直观的想到将A、C、G、T，分别对应：00,01,10,11，因此一个10个字母组成的子串，就可以表示为20个比特的int;

解题：

1、对原字符串进行遍历，每读一个字符，将其转为2位的bit值，并记录在int的对应位上；

2、读到10位之后，加入hash表中，并继续读取；当hash表中已经有对应数字存在，则为重复的字符串，记录在返回数组中；注意避免记录多次重复的字符串；

代码优化：

1、由于hash表只需记录当前值是否只出现一次，所以使用<int, bool>的键值对类型就可以了，bool变量true则只出现一次，出现其他次false;

2、虽然开始将ACGT转为00/01/10/11，但是发现重复后，不需要再转回来，因为字符串是顺序遍历的，遍历到重复后，包括当前遍历字符在内的前10个字符就是重复的子字符串；

3、每次ACGT转化，也会产生一定开销，由于ACGT的ASCII码值后三位分别为：001/011/111/100互不相同，而使用3个bit表示一个字母，10个字母30bit不会超过int的范围；因此使用三个bit来表示字母较好；

代码：

 1 class Solution {
 2 public:
 3     vector<string> findRepeatedDnaSequences(string s) {
 4         unordered_map<int, bool> hmap;
 5         vector<string> ret;
 6         int dna_bit = 0;
 7         int bits_cut = 0x3FFFFFFF;
 8         
 9         for (int i = 0; i < s.length() && i < 9; ++i) {
10             dna_bit = (dna_bit << 3) | (s[i] & 7);
11         }
12         
13         for (int i = 0; i < s.length(); ++i) {
14             dna_bit = (dna_bit << 3) | (s[i] & 7);
15             dna_bit = dna_bit & bits_cut;
16             if (hmap.find(dna_bit) != hmap.end()) { 
17                 if (hmap[dna_bit]) {
18                     ret.push_back(s.substr(i - 9, 10));
19                     hmap[dna_bit] = false;
20                 }
21             } else {
22                 hmap[dna_bit] = true;
23             }
24         }
25         
26         return ret;    
27     }
28 };

另：

还可以将第一个循环去除，因为ACGT字母后三位都不全为0，所以如果字母不到10个在hash表中肯定是唯一的，如果hash表插入的开销很小，可以省略第一个循环，本文中没有省略；

附录：

C++ hash表高效使用