187. 重复的 DNA 序列

🟠   🔖  位运算 哈希表 字符串 滑动窗口 哈希函数 滚动哈希  🔗 力扣 LeetCode

题目

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 <= 10^5
• s[i] is either 'A', 'C', 'G', or 'T'.

题目大意

DNA 序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

• 例如，"ACGAATTCCG" 是一个 DNA 序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA 序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入： s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

输入： s = "AAAAAAAAAAAAA"

输出：["AAAAAAAAAA"]

提示：

• 0 <= s.length <= 10^5
• s[i]``==``'A'、'C'、'G' or 'T'

解题思路

1. 滑动窗口获取长度为 10 的子串：

   • 使用一个长度为 10 的滑动窗口，遍历字符串 s。
   • 对每个窗口内的子串进行处理。

2. 使用集合记录子串出现情况：

   • 使用两个 Set：
     • subSet 记录所有已扫描到的子串。
     • res 记录重复出现的子串。
   • 对于每个子串：
     • 如果已经在 subSet 中且不在 res 中，将其加入 res。
     • 否则，将其加入 subSet。

3. 返回结果：

   • 将 res 中的子串转换为数组并返回。

复杂度分析

• 时间复杂度：O(n)，遍历字符串一次，窗口大小为 10，每次取子串的复杂度为 O(10)，总复杂度为 O((n - 10) * 10)，简化为 O(n)。
• 空间复杂度：O(n)，使用两个 Set 存储子串，最坏情况下存储 O(n) 个长度为 10 的字符串。

代码

/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function (s) {
	const n = s.length;
	let res = new Set();
	let subSet = new Set();

	// 遍历所有长度为 10 的子串
	for (let i = 0; i <= n - 10; i++) {
		const substr = s.slice(i, i + 10);

		// 如果子串已经在 subSet 中且不在 res 中，则加入 res
		if (subSet.has(substr)) {
			res.add(substr);
		} else {
			subSet.add(substr);
		}
	}

	// 返回结果数组
	return [...res];
};