[LeetCode] Repeated DNA Sequences-蒲公英云

[LeetCode] Repeated DNA Sequences

Repeated DNA Sequences
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”,

Return:

[“AAAAACCCCC”, “CCCCCAAAAA”].

思路：

1、使用哈希表，键为10个字符，值为出现次数；

2、定义一个res链表，存放符合要求的串；

3、符合要求的串为：在哈希表中出现，并且在res中不存在。

错误思路：全部存储在哈希表中，若哈希表中已存在，则值加1,；再遍历一次哈希表，取出所有值大于1的串 ==> 内存超出限制, Memory Limit Exceeded

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
       Map<String, Integer> mmap = new HashMap<String, Integer>();
        List<String> res = new ArrayList<String>() ;
        for(int i = 0; i < s.length()-9; i ++){
            String sub = s.substring(i, i + 10) ;
            if(mmap.containsKey(sub) && !res.contains(sub)) {
                res.add(sub) ;
            }else{
                mmap.put(sub, 1) ;
            }
        }
        return res ;
    }
}