重复的DNA序列

题目链接

重复的DNA序列

题目描述

注意点

• 0 <= s.length <= 10^5
• s[i]==‘A’、‘C’、‘G’ or ‘T’
• 返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)

解答思路

• 使用一个大小为10的滑动窗口存储该区间内的字符组成的字符串，使用哈希表存储任意一段滑动窗口对应的字符串是否出现过，如果未出现则往哈希表中加入该字符串，如果出现过则还需要判断结果中是否已存在该字符串，不存在则往结果中添加字符串

代码

class Solution {public List<String> findRepeatedDnaSequences(String s) {if (s.length() <= 10) {return new ArrayList<>();}Set<String> res = new HashSet<>();StringBuilder sb = new StringBuilder();for (int i = 0; i < 10; i++) {sb.append(s.charAt(i));}Set<String> set = new HashSet<>();set.add(sb.toString());for (int i = 10; i < s.length(); i++) {sb.deleteCharAt(0);sb.append(s.charAt(i));String tmp = sb.toString();if (!set.add(tmp)) {res.add(tmp);}}return new ArrayList<>(res);}
}

关键点

• 滑动窗口的思想
• 防止多个满足题意的相同字符串重复添加