Leetcode No.187 重复的DNA序列（滑动窗口）
一、题目描述
所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
提示：
0 <= s.length <= 105
s[i] 为 'A'、'C'、'G' 或 'T'二、解题思路
线性时间窗口切片 + HashSet+HashMap
沿长度为 N 的字符串移动长度为 L 的滑动窗口。 检查滑动窗口中的序列是否在 HashMap中。 如果是，则找到了重复的序列，将序列假如到HashSet中。 否则，将序列添加到 HashMap中。
三、代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
HashSet<String> sites = new HashSet<String>();
HashMap map=new HashMap<>();
int n=s.length();
for(int i=0;i<n-9;i++){
String subStr=s.substring(i,i+10);
if(map.containsKey(subStr)){
sites.add(subStr);
}else{
map.put(subStr,1);
}
}
return new ArrayList<>(sites);
}
public static void main(String[] args) {
Solution solution=new Solution();
List<String> rs=solution.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
//List<String> rs=solution.findRepeatedDnaSequences("AAAAAAAAAAAAA");
for(String s:rs){
System.out.println(s);
}
}
}四、复杂度分析
时间复杂度：O((N−L)L)。在执行的循环中，有N−L+1 个长度为 L 的子字符串，这会导致 O((N−L)L) 时间复杂性。 空间复杂度：使用了 O((N−L)L) 去存储 HashSet，由于 L=10 最终为时间复杂度为O(N)。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/09/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
