描述 Description

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"].

[Repeated DNA Sequences]

分析 Analysis

方法1

窗口法

首先能想到一个简单直接的方法，用一个长度为10的窗口，从左到右扫描，放入 HashMap，并把计数器增一。最后，把 HashMap 中所有计数器大于1的字符串输出来。

时间复杂度 O(n), 由于HashMap中存储了所有长度为10的子串，所以空间复杂度O(10n)。

方法2

完美哈希

由于字符串中只存在 A, C, G, T 四种字符，我们可以把每个字符映射为2个bit:

A -> 00
C -> 01
G -> 10
T -> 11

每个长度为10的字符串，可以映射为 20 bits, 小于32位，因此可以把这个字符串映射到一个整数。这个方法时间复杂度依旧是O(n)，但空间复杂度下降到了O(n)（n代表字符占用内存的话，这里应该是O(4n)）。

方法3（推荐）

不是哈希，但是和哈希的原理是一样的，也是将10位字符串映射到int整数中保存，不过需要一些小技巧。

总共有4种可能的字符A, C, G 和 T，但是使用3个bits位来存储每个字符，这样10个字符的字符串需要30个bits（2个bits不用），同样也只需要1个int整数就可以保存10个字符串的映射（方法2是20个bits，有12个bits没用）。这样做的原因是可以更好地写出code，同时不需要哈希操作。

A, C, G, T的八进制表示 A is 0101, C is 0103, G is 0107, T is 0124. 4种字符八进制最后的一个数字（即二进制最后3位）都不同！

Note: 16进制分别对应为A is 0x41, C is 0x43, G is 0x47, T is 0x54。

我们可以使用s[i] & 7 得到最后的这个数字，只需要3bits存储。这样读入10个字符可以使用30个bits存储在一个int整数中，相当于对10长度字符串进行了一次hash。只要检测到此整数对应的map值已经是1了，就添加到结果中。还是不懂的话结合下面代码看吧。

时间复杂度O(n)，空间复杂度O(4n)。

方法3变种

Note: 小编发现即使使用2bits，也是可以不使用hash字符串 。看A, C, G, T二进制的后3位，A 001, C 011, G 111, T 100，通过s[i] >> 1 & 3 （或者(s[i] - 'A' + 1) % 5）就可以得到倒数第2-3位的两个bits，A 00, C 01, G 11, T 10，居然都是不同的！所以同样不使用直接hash还是可以只使用20个bits存储的。直接这样其实不如不使用这种变种。

时间复杂度O(n)，空间复杂度O(4n)。

但是变种方法如果使用bitmap方法，用字符bitmap就可以只使用24个bits(即3个char)存储，这样空间只需要O(3n)。

代码 Code

注意字符串<11的情况 。

方法3

vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<int, int> m;
    vector<string> r;
    int t = 0, i = 0, ss = s.size();
    int len = s.size(),hashNum = 0;
    if (ss < 11) return r;

    while (i < 9)
        t = t << 3 | s[i++] & 7;
    while (i < ss)
        if (m[t = t << 3 & 0x3FFFFFFF | s[i++] & 7]++ == 1)
            r.push_back(s.substr(i - 10, 10));
    return r;
}

方法3的变种

vector<string> findRepeatedDnaSequences(string s) {
    char  hashMap[1048576] = {0};
    vector<string> ans;
    int len = s.size(),hashNum = 0;
    if (len < 11) return ans;
    for (int i = 0;i < 9;++i)
        hashNum = hashNum << 2 | (s[i] - 'A' + 1) % 5;
    for (int i = 9;i < len;++i)
        if (hashMap[hashNum = (hashNum << 2 | (s[i] - 'A' + 1) % 5) & 0xfffff]++ == 1)
            ans.push_back(s.substr(i-9,10));
    return ans;
}