LeetCode 187 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"].
上來只能想到暴力搜索。。筷登。掃描字符串，對于每一個10bit的substring菲宴，check if除了這個substring以外，string的后半部分是否仍然含有這個substring趋急，可以用string.index(str)喝峦，若不是-1，則說明存在呜达。
但顯然超時了谣蠢。。查近。
為了防止每次都搜索一遍substring是否存在眉踱，不防將已經(jīng)出現(xiàn)過的10bit string放到一個hashset中，然后對于往后的substring霜威，都檢查是否出現(xiàn)過谈喳。這樣做的壞處是：存儲所有10bit string可能需要消耗過多內(nèi)存。
看discuss發(fā)現(xiàn)了很tricky的hashset+bit manipulation的方法戈泼。
bit manipulation真得挺難的婿禽，遇到這類題一直沒啥思路。大猛。扭倾。
對于搜索類的題，如果用hash map胎署，那有一個問題是吆录，再好的hash function，都可能存在collision琼牧，那為什么這題用hash，仍然可以避免collision呢哀卫？
這就是因為巨坊，本題的string只可能有4種字符（ATCG），再結(jié)合bit manipulation就可以創(chuàng)造一種不發(fā)生沖突的方式此改！
同時減少memory storage趾撵，因為直接存10bit的substring，太浪費內(nèi)存了！Ｕ嫉鳌暂题！
我們希望盡量減少存儲所用的bit數(shù)量，而因為僅有4種字符究珊，考慮使用兩位二進制數(shù)薪者，表示這四個字符！＝虽獭言津！
0 = 00 (bits in binary number system) = 'A'
1 = 01 (bits in binary number system) = 'C'
2 = 10 (bits in binary number system) = 'G'
3 = 11 (bits in binary number system) = 'T'
因此10bit的substring只需要10*2=20位，就可以表示取试，而一般的integer都需要4bytes也就是32位悬槽。
以"AACCTCCGGT" 為例：
A A C C T C C G G T
00 00 01 01 11 01 01 10 10 11 = 00000101110101101011 (binary) = 23915 (decimal)
用兩個hashset分別存儲出現(xiàn)過的substring，和已經(jīng)出現(xiàn)過兩次的substring瞬浓，某substring出現(xiàn)第二次時初婆，將其加入結(jié)果list中。
注意這里v就是20bit的string轉(zhuǎn)成的數(shù)猿棉，用于存儲在hashset中０跖选！铺根！
這里運用到左移與或運算宪躯，還有0xfffff的mask運算。
Set<Integer> seq = new HashSet<>();
Set<Integer> repeatedSeq = new HashSet<>();
v = (v<<2 | map.get(s.charAt(i))) & 0xfffff;
if (!seq.add(v) && repeatedSeq.add(v))
代碼：
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> seqs = new ArrayList<>();
Set<Integer> seq = new HashSet<>();
Set<Integer> repeatedSeq = new HashSet<>();
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
map.put('A',0);
map.put('C',1);
map.put('G',2);
map.put('T',3);
int v = 0;
// Use a sliding window to check every 10-bit substring
for (int i = 0; i < s.length(); i++) {
// 2 bits/char * 10 char = 20 bits so use 0xfffff
v = (v<<2 | map.get(s.charAt(i))) & 0xfffff;
if (i < 9) continue;
// Check each 10-bit substring
else {
// If first come out duplicates, then add to list
if (!seq.add(v) && repeatedSeq.add(v))
seqs.add(s.substring(i-9, i+1));
}
}
return seqs;
}
}
參考：
https://discuss.leetcode.com/topic/8894/clean-java-solution-hashmap-bits-manipulation/9
