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.
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Solution: count the frequency of 10 letter words
class Solution {
//find all the 10-letter-long sequences that occur more than once in a DNA molecule
public List<String> findRepeatedDnaSequences(String s) {
//substring -- subset n +n-1+...+1: n-k+1
List<String> res = new ArrayList<String>();
Map<String,Integer> map = new HashMap<String,Integer>();
int n = s.length();
int k =10;
if(n < k) return res;
for(int i = 0; i<=n-k; i++){//11-10 1
String sub = s.substring(i, i+k);
if(map.containsKey(sub)){
map.put(sub, map.get(sub)+1);
}else {
map.put(sub, 1);
}
}
for(Map.Entry<String, Integer> entry : map.entrySet()){
if(entry.getValue() >1){
res.add(entry.getKey());
}
}
return res;
}
}Solution 2: two HashSet with a non-duplicate feature.
public List<String> findRepeatedDnaSequences(String s) {
Set seen = new HashSet(), repeated = new HashSet();
for (int i = 0; i + 9 < s.length(); i++) {
String ten = s.substring(i, i + 10);
if (!seen.add(ten))//if add then first time, else add it
repeated.add(ten);
}
return new ArrayList(repeated);
}subsequence & substring
subsequence: subset 2^n
substring: continous string : n+n-1+n-2+...+1