LeetCode 187. Repeated DNA Sequences（重複DNA序列）

原題網址：https://leetcode.com/problems/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"].      

方法：使用哈希集合來檢查是否重複。

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> set = new HashSet<>();
        List<String> sequences = new ArrayList<>();
        Set<String> found = new HashSet<>();
        for(int i=0; i+10<=s.length(); i++) {
            String sub = s.substring(i, i+10);
            if (set.contains(sub) && !found.contains(sub)) { sequences.add(sub); found.add(sub);}
            else set.add(sub);
        }
        return sequences;
    }
}