- 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"].
Subscribe to see which companies asked this question
1）直接在哈希表中存入10個字符惡毒字符串柿扣。
RE?
超過限額內(nèi)存？
2）用兩個Bit保存一個核苷酸窝革，20Bit保存十個字符瘟斜，用一個int即可背犯。
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Map<Character,Integer> charMap = new HashMap<>();
charMap.put('A',0);
charMap.put('C',1);
charMap.put('G',2);
charMap.put('T',3);
Map<Integer,Integer> seqMap = new HashMap<>();
List<String> result = new ArrayList<String>();
int sum = 0;
for(int i=0; i<s.length(); i++) {
sum = ((sum << 2) + charMap.get(s.charAt(i))) ;
sum = sum & 0xFFFFF;
if(i < 9) continue;
Integer v = seqMap.get(sum);
if(v!=null && v==1){
result.add(s.substring(i-9,i+1));
}
seqMap.put(sum, v!=null?v+1:1);
}
return result;
}
}
