187. 重复的DNA序列
题目描述
DNA 序列是只由字母 'A'、'C'、'G'、'T' 组成的字符串，例如 "ACGAATTCCG"。
输入一个 DNA 序列 s。找出所有长度为 10、在 s 中出现至少两次的子串（出现位置可以重叠）。
每个这样的子串只返回一次，顺序任意。
示例 1
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC","CCCCCAAAAA"]
解释："AAAAACCCCC" 和 "CCCCCAAAAA" 都各出现了两次。
示例 2
输入：s = "AAAAAAAAAAAAA" 输出：["AAAAAAAAAA"]
解释：13 个 A 中，长度为 10 的全 A 子串出现了 4 次，只返回一次。
数据范围
0 <= s.length <= 10^5s[i]为'A'、'C'、'G'或'T'。
解题思路：哈希表记录子串
用一个长度固定为 10 的窗口从左到右滑过 s。集合 seen 记录见过的窗口内容：如果当前子串已在 seen 中，说明它至少出现第二次，放进结果集合 res；否则加入 seen。res 也用集合，保证出现三次以上的子串只输出一次。
为什么正确
处理完起点 i 后，seen 是 s[0..i+9] 中所有长 10 的子串，res 是其中出现至少两次的子串。
复杂度分析
时间 O(10n)，空间 O(10n)。若把每个字母编成 2 位，可以用滚动整数把时间降到 O(n)。
易错点
结果用列表直接追加会把出现 3 次的子串输出两次。另外循环上界是 len(s) - 9，写成 len(s) - 10 会漏掉最后一个窗口。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
seen, res = set(), set()
for i in range(len(s) - 9):
sub = s[i:i + 10]
if sub in seen:
res.add(sub)
else:
seen.add(sub)
return list(res)class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Set<String> seen = new HashSet<>(), res = new HashSet<>();
for (int i = 0; i + 10 <= s.length(); i++) {
String sub = s.substring(i, i + 10);
if (seen.contains(sub)) {
res.add(sub);
} else {
seen.add(sub);
}
}
return new ArrayList<>(res);
}
}class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_set<string> seen, res;
for (int i = 0; i + 10 <= (int)s.size(); i++) {
string sub = s.substr(i, 10);
if (seen.count(sub)) {
res.insert(sub);
} else {
seen.insert(sub);
}
}
return vector<string>(res.begin(), res.end());
}
};func findRepeatedDnaSequences(s string) []string {
seen, res := map[string]bool{}, map[string]bool{}
for i := 0; i+10 <= len(s); i++ {
sub := s[i : i+10]
if seen[sub] {
res[sub] = true
} else {
seen[sub] = true
}
}
out := []string{}
for k := range res {
out = append(out, k)
}
return out
}/**
* @param {string} s
* @return {string[]}
*/
var findRepeatedDnaSequences = function(s) {
const seen = new Set(), res = new Set();
for (let i = 0; i + 10 <= s.length; i++) {
const sub = s.substring(i, i + 10);
if (seen.has(sub)) {
res.add(sub);
} else {
seen.add(sub);
}
}
return [...res];
};function findRepeatedDnaSequences(s: string): string[] {
const seen = new Set<string>(), res = new Set<string>();
for (let i = 0; i + 10 <= s.length; i++) {
const sub = s.substring(i, i + 10);
if (seen.has(sub)) {
res.add(sub);
} else {
seen.add(sub);
}
}
return [...res];
}其他解法
主解法每步取出长度 L=10 的子串做哈希，是 O(NL)；位运算编码把子串压成一个整数并滑动更新，降到 O(N)。
解法 2：滑动窗口 + 位运算编码 时间 O(N)，空间 O(N)
把 A、C、G、T 分别编码为 0–3，每个字符占 2 位，长度 10 的子串正好对应一个 20 位整数。窗口右移时，把编码左移 2 位、拼上新字符、再与 (1<<20)-1 取与去掉最早的字符，O(1) 得到新编码。哈希表以整数为键计数，计数刚好变成 2 时把该子串加入答案。
避免了每步复制和哈希长度为 10 的字符串，是滑动窗口编码的典型例子。依赖字符集只有 4 种，代码比直接存子串更难写对。
from typing import List
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
code = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
mask = (1 << 20) - 1
cnt = {}
res = []
x = 0
for i, ch in enumerate(s):
x = ((x << 2) | code[ch]) & mask
if i >= 9:
cnt[x] = cnt.get(x, 0) + 1
if cnt[x] == 2:
res.append(s[i - 9:i + 1])
return resclass Solution {
public List<String> findRepeatedDnaSequences(String s) {
Map<Character, Integer> code = Map.of('A', 0, 'C', 1, 'G', 2, 'T', 3);
final int mask = (1 << 20) - 1;
Map<Integer, Integer> cnt = new HashMap<>();
List<String> res = new ArrayList<>();
int x = 0;
for (int i = 0; i < s.length(); i++) {
x = ((x << 2) | code.get(s.charAt(i))) & mask;
if (i >= 9 && cnt.merge(x, 1, Integer::sum) == 2) res.add(s.substring(i - 9, i + 1));
}
return res;
}
}class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<char, int> code = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
const int mask = (1 << 20) - 1;
unordered_map<int, int> cnt;
vector<string> res;
int x = 0;
for (int i = 0; i < (int)s.size(); i++) {
x = ((x << 2) | code[s[i]]) & mask;
if (i >= 9 && ++cnt[x] == 2) res.push_back(s.substr(i - 9, 10));
}
return res;
}
};func findRepeatedDnaSequences(s string) []string {
code := map[byte]int{'A': 0, 'C': 1, 'G': 2, 'T': 3}
const mask = 1<<20 - 1
cnt := map[int]int{}
res := []string{}
x := 0
for i := 0; i < len(s); i++ {
x = (x<<2 | code[s[i]]) & mask
if i >= 9 {
cnt[x]++
if cnt[x] == 2 {
res = append(res, s[i-9:i+1])
}
}
}
return res
}var findRepeatedDnaSequences = function(s) {
const code = { A: 0, C: 1, G: 2, T: 3 };
const mask = (1 << 20) - 1;
const cnt = new Map();
const res = [];
let x = 0;
for (let i = 0; i < s.length; i++) {
x = ((x << 2) | code[s[i]]) & mask;
if (i >= 9) {
const c = (cnt.get(x) || 0) + 1;
cnt.set(x, c);
if (c === 2) res.push(s.slice(i - 9, i + 1));
}
}
return res;
};function findRepeatedDnaSequences(s: string): string[] {
const code: Record<string, number> = { A: 0, C: 1, G: 2, T: 3 };
const mask = (1 << 20) - 1;
const cnt = new Map<number, number>();
const res: string[] = [];
let x = 0;
for (let i = 0; i < s.length; i++) {
x = ((x << 2) | code[s[i]]) & mask;
if (i >= 9) {
const c = (cnt.get(x) ?? 0) + 1;
cnt.set(x, c);
if (c === 2) res.push(s.slice(i - 9, i + 1));
}
}
return res;
};