[Leetcode]07/09 [Hash]Repeated DNA Sequences

/* HashMap to store decimal value of sequence to check if any two sequence has the same decimal value Method1: Time:O(n); Space:O(n) Logic: Binary 1. A=00, C=01, G=10 , T=11 2. AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT => 00000000000001010101010100000000101001.. 3. AAACCC = 00 00 00 01 01 01 = 21 4. check value 21 repeated or not in the map NOTE: 0xFFFFF = 2*10 =20 digits (sum<<2 class="brush:java;" data-blogger-escaped-0001="" data-blogger-escaped-0011="" data-blogger-escaped-0100="" data-blogger-escaped-0101="" data-blogger-escaped-0111="" data-blogger-escaped-0x3fffffff="" data-blogger-escaped-0xfffff="" data-blogger-escaped-1.="" data-blogger-escaped-1="" data-blogger-escaped-2.="" data-blogger-escaped-7="" data-blogger-escaped-:="" data-blogger-escaped-a:="" data-blogger-escaped-ascii="" data-blogger-escaped-blog="" data-blogger-escaped-c:="" data-blogger-escaped-character="" data-blogger-escaped-cnt="" data-blogger-escaped-digit="" data-blogger-escaped-digits="" data-blogger-escaped-every="" data-blogger-escaped-g:="" data-blogger-escaped-given="" data-blogger-escaped-http:="" data-blogger-escaped-https:="" data-blogger-escaped-i-9="" data-blogger-escaped-i="" data-blogger-escaped-last="" data-blogger-escaped-logic:="" data-blogger-escaped-map.get="" data-blogger-escaped-map="" data-blogger-escaped-method2:="" data-blogger-escaped-n="" data-blogger-escaped-need="" data-blogger-escaped-note:="" data-blogger-escaped-null="" data-blogger-escaped-only="" data-blogger-escaped-pre="" data-blogger-escaped-refereence:="" data-blogger-escaped-represent="" data-blogger-escaped-res.add="" data-blogger-escaped-return:="" data-blogger-escaped-s.charat="" data-blogger-escaped-s.substring="" data-blogger-escaped-s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" data-blogger-escaped-space:o="" data-blogger-escaped-sum="" data-blogger-escaped-summap.put="" data-blogger-escaped-t:="" data-blogger-escaped-the="" data-blogger-escaped-three="" data-blogger-escaped-time:o="" data-blogger-escaped-to="" data-blogger-escaped-wiki="" data-blogger-escaped-yuanhsh.iteye.com="" data-blogger-escaped-zh.wikipedia.org=""> public class Solution { public List findRepeatedDnaSequences(String s) { /* Method1: List res = new ArrayList(); Map map = new HashMap(); map.put('A', 0); map.put('C', 1); map.put('G', 2); map.put('T', 3); Map sumMap = new HashMap(); int sum = 0; for ( int i = 0; i < s.length(); i++ ) { // 00 00 00 01 01 01 // MSB LSB // i = 0, 3 & 0XFFFFF = 11 // i = 1, 11 00(11<<2 data-blogger-escaped-00="" data-blogger-escaped-01="" data-blogger-escaped-0xfffff="" data-blogger-escaped-10-letter-long="" data-blogger-escaped-10="" data-blogger-escaped-11="" data-blogger-escaped-1="" data-blogger-escaped-2="" data-blogger-escaped-9="" data-blogger-escaped-cnt="" data-blogger-escaped-continue="" data-blogger-escaped-i-9="" data-blogger-escaped-i="" data-blogger-escaped-if="" data-blogger-escaped-integer="" data-blogger-escaped-list="" data-blogger-escaped-map.get="" data-blogger-escaped-method2:="" data-blogger-escaped-null="" data-blogger-escaped-record="" data-blogger-escaped-res.add="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-s.charat="" data-blogger-escaped-s.substring="" data-blogger-escaped-sequence="" data-blogger-escaped-sum="" data-blogger-escaped-summap.put="" data-blogger-escaped-tring=""> res = new ArrayList(); HashMap sumMap = new HashMap(); int sum = 0; for ( int i = 0; i < s.length(); i++ ) { sum = ( (sum<<3 data-blogger-escaped-0x3fffffff="" data-blogger-escaped-10-letter-long="" data-blogger-escaped-7="" data-blogger-escaped-9="" data-blogger-escaped-cnt="" data-blogger-escaped-continue="" data-blogger-escaped-i-9="" data-blogger-escaped-i="" data-blogger-escaped-if="" data-blogger-escaped-integer="" data-blogger-escaped-null="" data-blogger-escaped-pre="" data-blogger-escaped-record="" data-blogger-escaped-res.add="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-s.charat="" data-blogger-escaped-s.substring="" data-blogger-escaped-sequence="" data-blogger-escaped-sum="" data-blogger-escaped-summap.put="">