187. Repeated DNA Sequences

The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.

For example, “ACGAATTCCG” is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

Example 1:

1 2	Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

1 2	Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]

在字串中找10個重複子字串。

TC: O(n), SC: O(n)  

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
    
        // set avoid duplicate substring    
        Set seen = new HashSet(), res = new HashSet();
            
     	if( s == null || s.length() < 10 )
            return new ArrayList(res);

        for (int i = 0; i <= s.length() - 10; i++) {
            String subStr = s.substring(i, i + 10); // Before Java 1.7.0_06: O(1), after Java 1.7.0_06: O(n) prevent memory leak
            if (!seen.add(subStr)) // add O(1)
                res.add(subStr);
        }
        return new ArrayList(res);
    }
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)