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"].
这道题的要求是在只含有AGCT的字符串中找出所有重复出现过的长度为10的子字符串。
找出重复出现的字符串，直接考虑就是Hash，对每个长度为10的字符串进行Hash并统计出现次数，这样遍历一遍字符串即可。可是Hash的时候会占用太多内存，导致“Memory Limit Exceeded”。
那么应该如何处理？可以注意到只有4个字符AGCT，而且每个字符的ASCII分别为：
A -> 65 -> 01000001
G -> 71 -> 01000111
C -> 67 -> 01000011
T -> 84 -> 01010100
发现了吧，这四个字符ASCII的二进制的最后3位不同。又由于要找出重复的长度为10的字串，因此可以用30个二进制位来表示这个字符串，也就是一个int类型刚好可以（不知道找出长度为10的是不是这么故意设计的）。接下来再对每个字串对应的int数字进行Hash统计数目即可。
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
vector<string> findRepeatedDnaSequences(string s)
{
unordered_map<int, int> m;
vector<string> vs;
// t用于记录10个字符的子串对应的数字（只用到了后30位）
int t = 0, i = 0;
while(i < 9) // 将前9个字符放入t中
t = t << 3 | s[i ++] & 7;
// 每次t左移3位后清空最高两位（t<<3&0x3FFFFFFF）
// 然后再读取下一个字符并取其末3位（s[i]&7）
// 最后将这3位放到t的末3位上（(t<<3&0x3FFFFFFF)|(s[i]&7)）
while(i < s.size())
if(m[t = t << 3 & 0x3FFFFFFF | s[i ++] & 7] ++ == 1)
vs.push_back(s.substr(i - 10, 10));
return vs;
}
};
其实，由于AGCT的末3位没有000，所有前面9个字符无需预先放入t中，可以统一处理，以缩短代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution
{
public:
vector<string> findRepeatedDnaSequences(string s)
{
unordered_map<int, int> m;
vector<string> vs;
for(int i = 0, t = 0; i < s.size(); i ++)
if(m[t = t << 3 & 0x3FFFFFFF | s[i] & 7] ++ == 1)
vs.push_back(s.substr(i - 9, 10));
return vs;
}
};