LeetCode--187. Repeated DNA Sequences

题目链接：https://leetcode.com/problems/repeated-dna-sequences/

要求寻找长度为10的DNA重复子字符串

思路一：这里可以考虑一个HashMap来存储出现的子字符串及其出现次数，出现第二次的则加入最终答案中，而首次出现的就加入Hashmap中，三次及三次以上出现的不加入只是更新出现次数。思路比较朴素，代码如下：

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        LinkedList<String> ret=new LinkedList<String>();
        HashMap<String,Integer> hs=new HashMap<String,Integer>();
        for(int i=0;i<s.length()-9;i++)
        {
                int j=i+9;
                String str=s.substring(i,j+1);
                if(hs.containsKey(str))
                {
                    int frequency=hs.get(str);
                    if(frequency==1)
                        ret.add(str);
                    hs.put(str,frequency+1);
                }
                else
                {
                    hs.put(str,1);
                }
        }
        return ret;
    }
}

时间复杂度：O（10m）=O(m)

空间复杂度：O（m）

这个解法效率也很一般。

思路二：总体方法就是来判重。上述思路可以再进一步简化，可以用一个HashSet来存储所有已经出现的子字符串，然后将重复出现的子字符串存到另一个HashSet中，这样就不用管它到底第几次出现了，因为重复出现的子字符串是无法插入集合中的，代码如下：

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> seen = new HashSet<>();
        HashSet<String> reap = new HashSet<>();
        for(int i=0; i<s.length()-9;i++) {
            String temp = s.substring(i,i+10);
            if(!seen.add(temp)) {
                reap.add(temp);
            }
        }
        
        return new ArrayList(reap);
    }
 }