原文链接: https://leetcode-cn.com/problems/repeated-dna-sequences
英文原文
The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
- For example,
"ACGAATTCCG"is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"]
Example 2:
Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]
Constraints:
1 <= s.length <= 105s[i]is either'A','C','G', or'T'.
中文题目
所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA" 输出：["AAAAAAAAAA"]
提示：
0 <= s.length <= 105s[i]为'A'、'C'、'G'或'T'
通过代码
高赞题解
滑动窗口 + 哈希表
数据范围只有 $10^5$，一个朴素的想法是：从左到右处理字符串 $s$，使用滑动窗口得到每个以 $s[i]$ 为结尾且长度为 $10$ 的子串，同时使用哈希表记录每个子串的出现次数，如果该子串出现次数超过一次，则加入答案。
为了防止相同的子串被重复添加到答案，而又不使用常数较大的 Set 结构。我们可以规定：当且仅当该子串在之前出现过一次（加上本次，当前出现次数为两次）时，将子串加入答案。
代码：
[]class Solution { public List<String> findRepeatedDnaSequences(String s) { List<String> ans = new ArrayList<>(); int n = s.length(); Map<String, Integer> map = new HashMap<>(); for (int i = 0; i + 10 <= n; i++) { String cur = s.substring(i, i + 10); int cnt = map.getOrDefault(cur, 0); if (cnt == 1) ans.add(cur); map.put(cur, cnt + 1); } return ans; } }
- 时间复杂度：每次检查以 $s[i]$ 为结尾的子串，需要构造出新的且长度为 $10$ 的字符串。令 $C = 10$，复杂度为 $O(n * C)$
- 空间复杂度：长度固定的子串数量不会超过 $n$ 个。复杂度为 $O(n)$
字符串哈希 + 前缀和
子串长度为 $10$，因此上述解法的计算量为 $10^6$。
若题目给定的子串长度大于 $100$ 时，加上生成子串和哈希表本身常数操作，那么计算量将超过 $10^7$，会 TLE。
因此一个能够做到严格 $O(n)$ 的做法是使用「字符串哈希 + 前缀和」。
具体做法为，我们使用一个与字符串 $s$ 等长的哈希数组 $h[]$，以及次方数组 $p[]$。
由字符串预处理得到这样的哈希数组和次方数组复杂度为 $O(n)$。当我们需要计算子串 $s[i…j]$ 的哈希值，只需要利用前缀和思想 $h[j] - h[i - 1] * p[j - i + 1]$ 即可在 $O(1)$ 时间内得出哈希值（与子串长度无关）。
到这里，还有一个小小的细节需要注意：如果我们期望做到严格 $O(n)$，进行计数的「哈希表」就不能是以 String 作为 key，只能使用 Integer（也就是 hash 结果本身）作为 key。因为 Java 中的 String 的 hashCode 实现是会对字符串进行遍历的，这样哈希计数过程仍与长度有关，而 Integer 的 hashCode 就是该值本身，这是与长度无关的。
代码：
[]class Solution { int N = (int)1e5+10, P = 131313; int[] h = new int[N], p = new int[N]; public List<String> findRepeatedDnaSequences(String s) { int n = s.length(); List<String> ans = new ArrayList<>(); p[0] = 1; for (int i = 1; i <= n; i++) { h[i] = h[i - 1] * P + s.charAt(i - 1); p[i] = p[i - 1] * P; } Map<Integer, Integer> map = new HashMap<>(); for (int i = 1; i + 10 - 1 <= n; i++) { int j = i + 10 - 1; int hash = h[j] - h[i - 1] * p[j - i + 1]; int cnt = map.getOrDefault(hash, 0); if (cnt == 1) ans.add(s.substring(i - 1, i + 10 - 1)); map.put(hash, cnt + 1); } return ans; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
我猜你问
- 字符串哈希的「构造 $p$ 数组」和「计算哈希」的过程，不会溢出吗？
会溢出，溢出就会变为负数，当且仅当两个哈希值溢出程度与 Integer.MAX_VALUE 呈不同的倍数关系时，会产生错误结果（哈希冲突），此时考虑修改 $P$ 或者采用表示范围更大的 long 来代替 int。
如果某些语言在 LeetCode 溢出报错的话，那么还需要手动取模一下。
- $P = 131313$ 这个数字是怎么来的？
WA 出来的，刚开始使用的 $P = 131$，被卡在了 $30/31$ 个样例。
字符串哈希本身存在哈希冲突的可能，一般会在尝试 $131$ 之后尝试使用 $13131$，然后再尝试使用比 $13131$ 更大的质数。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 78941 | 151312 | 52.2% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
