187. 重复的DNA序列
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 <= 105
s[i]==‘A’、‘C’、‘G’ or ‘T’
1. 我的解答
思路:滑动窗口,使用两个set存储截断的字符串,若第一个set已存储过,第二次该字符串若已经被第一个set存储,则存储到第二个set,表示出现大于一次,然后封装为list返回。
class Solution {
static final int L = 10;
public List<String> findRepeatedDnaSequences(String s) {
int left = 0, right =0;
HashSet<String> firstSet = new HashSet<>();
HashSet<String> secondSet = new HashSet<>();
while(right<s.length()){
right++;
if(right-left == 10){
String sub = s.substring(left,right);
if(firstSet.contains(sub)){
secondSet.add(sub);
}else{
firstSet.add(sub);
}
left++;
}
}
return new ArrayList<String>(secondSet);
}
}
2. 官方解答
class Solution {
static final int L = 10;
public List<String> findRepeatedDnaSequences(String s) {
List<String> ans = new ArrayList<String>();
Map<String, Integer> cnt = new HashMap<String, Integer>();
int n = s.length();
for (int i = 0; i <= n - L; ++i) {
String sub = s.substring(i, i + L);
cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
if (cnt.get(sub) == 2) {
ans.add(sub);
}
}
return ans;
}
}