问题
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
如：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出：[“AAAAACCCCC”, “CCCCCAAAAA”]
解法
使用字典
序列做 key，出现次数作为 value，value大于1的即为重复的 DNA 序列。
时间复杂度：\(O(n)\)
1
2
3
4
5
6
7
8
9
10
11
12
def find_repeated_dna_sequences(s: str) -> list:
if len(s) <= 10:
return []
result = []
tmp = {}
for i in range(len(s) - 10 + 1):
a = s[i:i + 10]
tmp[a] = tmp.get(a, 0) + 1
if tmp[a] == 2:
result.append(a)
return result
使用容器
创建一个临时容器，set 或 list，遍历的字符串不在其中时，将字符串放入该临时容器中；在其中时，则该字符串为要找的字符串。
如果使用 set 的话，时间复杂度为：\(O(n)\)，a in tmp 语句是 \(O(1)\) 的时间复杂度，set 底层使用的哈希表。
如果使用 list 的话，时间复杂度：\(O({n^2})\)，a in tmp 语句是 \(O(n)\) 的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
def find_repeated_dna_sequences(s: str) -> list:
if len(s) <= 10:
return []
result = []
tmp = []
for i in range(len(s) - 10 + 1):
a = s[i:i + 10]
if a in tmp:
result.append(a)
else:
tmp.append(a)
return result
二进制
上面两种方法思想上本质上是一样的。两者都要依次遍历长度为10的子字符串，判断其是否已经出现过了。每次遍历，其实是字符串窗口滑动了一位，上一次和下一次的串有8个重复字符的，字符总共只有4种，因此可以使用二进制编码的方式压缩空间。
| 上一次 | A | A | A | A | A | C | C | C | C | C | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 下一次 | A | A | A | A | C | C | C | C | C | A |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def find_repeated_dna_sequences(s: str) -> list:
if len(s) <= 10:
# 长度不超过10的话，不会有重复的DNA串
return []
m = {
"A": 0, # 00
"C": 1, # 01
"G": 2, # 10
"T": 3, # 11
}
s_bin = [m.get(x) for x in s]
# 将字符串转换为数字，节省空间，下称"串数字"
key = 0
# 记录不重复的串数字
tmp = set()
# 对 key 进行初始化，长度为10
for i in range(10):
key = key << 2 | s_bin[i]
# 记录第一个串数字
tmp.add(key)
# 最终结果
result = set()
for i in range(10, len(s)):
# 对上一个字符串串左移一个字符，也即对上个串数字左移2位
key = key << 2
# 末尾2位替换为新遍历到的字符
key |= s_bin[i]
# 使用20位的掩码截取，0xfffff=1111 1111 1111 1111 1111
key &= 0xfffff
if key in tmp:
result.add(s[i - 9:i + 1])
else:
tmp.add(key)
return list(result)