所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的,例如 'ACTGGGC' 。
请你实现一个函数找出所有的目标子串,目标子串的定义是,长度等于 10 ,且在 DNA 序列中出现次数超过 1 次的子串(允许两个子串有重合的部分,如下面的示例2所示)。
(注:返回的所有目标子串的顺序必须与原DNA序列的顺序一致,如下面的示例1所示)
数据范围:DNA序列长度满足 ,保证序列中只出现 'A' , 'C' , 'G' , 'T'。
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
["AAAAACCCCC","CCCCCAAAAA"]
"AAAAACCCCC"和"CCCCCAAAAA"长度等于 10 且在DNA序列中分别出现了 2 次。 不能返回["CCCCCAAAAA","AAAAACCCCC"],因为在原DNA序列中,"AAAAACCCCC"要比"CCCCCAAAAA"先出现。
"AAAAAAAAAAA"
["AAAAAAAAAA"]
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param DNA string字符串 1 * @return string字符串一维数组 */ public String[] repeatedDNA (String DNA) { // write code here if(DNA.length() < 10) return new String[0]; HashSet<String> set = new HashSet<>(); ArrayList<String> res = new ArrayList<>(); for(int start = 0; start < DNA.length() - 9; start++){ String seq = DNA.substring(start, start + 10); if(set.contains(seq)){ // set中加过,表示这个DN***段出现超过1次,添加进结果集 if(!res.contains(seq)){ res.add(seq); } }else{ set.add(seq); } } return res.toArray(new String[res.size()]); } }