反向输出dna序列_[LeetCode]187. 重复的DNA序列

题目链接：https://leetcode-cn.com/problems/repeated-dna-sequences/

题目描述：

所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。

示例：

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

思路：

滑动窗口 + 哈希

每次取10个字符记录下来，然后记录个数

时间复杂度：

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        from collections import defaultdict
        visited = set()
        res = set()
        for i in range(0, len(s) - 9):
            tmp = s[i:i+10]
            if tmp in visited:
                res.add(tmp)
            visited.add(tmp)
        return list(res)
           

java

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set visited = new HashSet(), res = new HashSet();
        for (int i = 0; i + 10 <= s.length(); i++) {
            String tmp = s.substring(i, i + 10);
            if (visited.contains(tmp)) {
                res.add(tmp);
            } else visited.add(tmp);


        }
        return new ArrayList<>(res);
    }
}
           

同步更新博客：

一起刷LeetCode - 威行天下 - 博客园​www.cnblogs.com