[LeetCode] 187. 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 <= 105
s[i] is either ‘A’, ‘C’, ‘G’, or ‘T’.

重复的DNA序列。

DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。
例如，”ACGAATTCCG” 是一个 DNA序列 。在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/repeated-dna-sequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

给的 input 是一个 DNA 序列，请输出所有出现多次的 DNA 子序列。这题有位运算的做法但是感觉用 hashset 的做法更方便。注意 DNA 的定义是一个长度为 10 的子字符串。
思路是用两个 hashset，第一个存子序列是否出现过（seen），第二个存最后的输出（res）。当某个子序列在 seen 中已经有了，就存入 res；最后输出 res 里面所有的子序列。

复杂度

时间O(n) - n 是 input 字符串长度
空间O(n) - 用了两个 hashset

代码

Java实现

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> seen = new HashSet<>();
        HashSet<String> res = new HashSet<>();
        for (int i = 0; i < s.length() - 9; i++) {
            String str = s.substring(i, i + 10);
            if (!seen.add(str)) {
                res.add(str);
            }
        }
        return new ArrayList<>(res);
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function(s) {
	let seen = new Set();
	let res = new Set();
	for (let i = 0; i < s.length - 9; i++) {
		const str = s.substring(i, i + 10);
		if (seen.has(str)) {
			res.add(str);
		} else {
			seen.add(str);
		}
	}
	return Array.from(res);
};