refactor 115

fishercoder1534 · fishercoder1534 · commit 3ff568904150 · 2018-03-29T07:25:20.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_115.java b/src/main/java/com/fishercoder/solutions/_115.java
@@ -1,42 +1,44 @@
 package com.fishercoder.solutions;
 
-public class _115 {
-    /**This is a typical DP problem, illustrated in Jiuzhang.
-     * 
-     * I've drawn out the 2d matrix on the whiteboard:
-     * 
-     * 1. initialize a 2d matrix of size (m+1)*(n+1)
-     * 2. initialize row 0, it should be 1,0,0,0,0... this is because when S is an empty string, only when T is empty, it could be a subsequence
-     * 3. initialize column 0, it should be 1,1,1,1,1,1...
-     * 4. starting from (1,1)*/
+/**
+ * 115. Distinct Subsequences
+ *
+ * Given a string S and a string T, count the number of distinct subsequences of S which equals T. A
+ * subsequence of a string is a new string which is formed from the original string by deleting some
+ * (can be none) of the characters without disturbing the relative positions of the remaining
+ * characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
+ *
+ * Here is an example: S = "rabbbit", T = "rabbit" Return 3.
+ */
 
+public class _115 {
+  public static class Solution1 {
     public int numDistinct(String s, String t) {
-        int m = s.length();
-        int n = t.length();
-        int[][] dp = new int[m + 1][n + 1];
+      int m = s.length();
+      int n = t.length();
+      int[][] dp = new int[m + 1][n + 1];
 
-        char[] schar = s.toCharArray();
-        char[] tchar = t.toCharArray();
+      char[] schar = s.toCharArray();
+      char[] tchar = t.toCharArray();
 
-        for (int i = 0; i <= m; i++) {
-            dp[i][0] = 1;
-        }
+      for (int i = 0; i <= m; i++) {
+        dp[i][0] = 1;
+      }
 
-        for (int j = 1; j <= n; j++) {
-            dp[0][j] = 0;
-        }
+      for (int j = 1; j <= n; j++) {
+        dp[0][j] = 0;
+      }
 
-        for (int i = 1; i <= m; i++) {
-            for (int j = 1; j <= n; j++) {
-                if (schar[i - 1] == tchar[j - 1]) {
-                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
-                } else {
-                    dp[i][j] = dp[i - 1][j];
-                }
-            }
+      for (int i = 1; i <= m; i++) {
+        for (int j = 1; j <= n; j++) {
+          if (schar[i - 1] == tchar[j - 1]) {
+            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
+          } else {
+            dp[i][j] = dp[i - 1][j];
+          }
         }
-
-        return dp[m][n];
+      }
+      return dp[m][n];
     }
-
+  }
 }
diff --git a/src/test/java/com/fishercoder/_115Test.java b/src/test/java/com/fishercoder/_115Test.java
@@ -0,0 +1,21 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._115;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _115Test {
+  private static _115.Solution1 solution1;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _115.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    assertEquals(3, solution1.numDistinct("rabbbit", "rabbit"));
+  }
+}
