By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、

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

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

示例：

 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 输出：["AAAAACCCCC", "CCCCCAAAAA"]

1.1、解题思路

使用Set ，遍历字符串，每次返将10个长度的放入，如果重复的话说明是我们想要的，放到List中去，如果List存在就不放

1.2、算法

public List<String> findRepeatedDnaSequences(String s) {

    List<String> res = new ArrayList<>();
    if (s.length() <= 10) {
        return res;
    }

    HashSet<String> set = new HashSet<>();
    //保证i是起点的时候 有10个字符
    for (int i = 0; i + 10 <= s.length(); i++) {
        //包头不包尾，截取长度为10
        String str = s.substring(i, i + 10);
        //如果能添加则继续走，说明肯定是唯一的
        if (set.add(str)) {
            continue;
        }

        //，走到这里说明set 说明 str重复了 。加入结果集中不包含的
        if (!res.contains(str)) {
            res.add(str);
        }
    }
    return res;
}

1.3、测试

 @Test
    public void test(){
        System.out.println(findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
    }

​

ContactAuthor