add a solution for 187

fishercoder1534 · fishercoder1534 · commit a3b9465799ae · 2021-10-15T13:10:35.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_187.java b/src/main/java/com/fishercoder/solutions/_187.java
@@ -2,8 +2,10 @@
 
 import java.util.ArrayList;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 public class _187 {
     public static class Solution1 {
@@ -22,4 +24,46 @@ public List<String> findRepeatedDnaSequences(String s) {
             return repeatedSequences;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * Use Rolling Hash/Rabin-Karp algorithm to significantly speed up the search.
+         *
+         * Rolling Hash/Rabin-Karp algorithm:
+         * Instead of comparing the entire string to the other, we compare only the hash after adding the incoming character
+         * and removing the outgoing character, this could be done in constant time.
+         * Back to this problem, since there are only 4 characters, we only need 2 bits to represent each character:
+         * 00 -> A
+         * 01 -> C
+         * 10 -> G
+         * 11 -> T
+         * so for a DNA sequence that is 10 character long, a total of 10 * 2 = 20 bits is good enough, this is much smaller than
+         * an Integer (32-bit) in most modern programming languages, so using one integer could well represent one DNA sequence.
+         * Thus we could do bit manipulation to implement the removal of the outgoing character and the addition of the incoming character.
+         *
+         * <<= 2 will shift the integer to the left, i.e. removing the outgoing character;
+         * |= val will add the incoming character.
+         */
+        public List<String> findRepeatedDnaSequences(String s) {
+            Set<Integer> seen1stTime = new HashSet<>();
+            Set<Integer> seen2ndTime = new HashSet<>();
+            List<String> ans = new ArrayList<>();
+            char[] map = new char[26];
+            map['A' - 'A'] = 0;
+            map['C' - 'A'] = 1;
+            map['G' - 'A'] = 2;
+            map['T' - 'A'] = 3;
+            for (int i = 0; i < s.length() - 9; i++) {
+                int hash = 0;
+                for (int j = i; j < i + 10; j++) {
+                    hash <<= 2;
+                    hash |= map[s.charAt(j) - 'A'];
+                }
+                if (!seen1stTime.add(hash) && seen2ndTime.add(hash)) {
+                    ans.add(s.substring(i, i + 10));
+                }
+            }
+            return ans;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_187Test.java b/src/test/java/com/fishercoder/_187Test.java
@@ -11,23 +11,32 @@
 import static org.junit.Assert.assertEquals;
 
 public class _187Test {
-  private static _187.Solution1 solution1;
-  private static String s;
-  private static List<String> expected;
-  private static List<String> actual;
+    private static _187.Solution1 solution1;
+    private static _187.Solution2 solution2;
+    private static String s;
+    private static List<String> expected;
 
-  @BeforeClass
-  public static void setup() {
-    solution1 = new _187.Solution1();
-  }
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _187.Solution1();
+        solution2 = new _187.Solution2();
+    }
 
-  @Test
-  public void test1() {
-    s = "AAAAAAAAAAA";
-    System.out.println(s.length());
-    actual = solution1.findRepeatedDnaSequences(s);
-    expected = new ArrayList<>(Arrays.asList("AAAAAAAAAA"));
-    System.out.println(expected.get(0).length());
-    assertEquals(expected, actual);
-  }
+    @Test
+    public void test1() {
+        s = "AAAAAAAAAAA";
+        System.out.println(s.length());
+        expected = new ArrayList<>(Arrays.asList("AAAAAAAAAA"));
+        assertEquals(expected, solution1.findRepeatedDnaSequences(s));
+        assertEquals(expected, solution2.findRepeatedDnaSequences(s));
+    }
+
+    @Test
+    public void test2() {
+        s = "AAAAAAAAAAAAA";
+        System.out.println(s.length());
+        expected = new ArrayList<>(Arrays.asList("AAAAAAAAAA"));
+        assertEquals(expected, solution1.findRepeatedDnaSequences(s));
+        assertEquals(expected, solution2.findRepeatedDnaSequences(s));
+    }
 }
