package com.fishercoder.solutions;

/**
 * 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];

      char[] schar = s.toCharArray();
      char[] tchar = t.toCharArray();

      for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;
      }

      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];
          }
        }
      }
      return dp[m][n];
    }
  }
}

@@ -33,485 +33,8 @@
 s;%0A%0A
-/**%0A * 115. Distinct Subsequences%0A *%0A * Given a string S and a string T, count the number of distinct subsequences of S which equals T. A%0A * subsequence of a string is a new string which is formed from the original string by deleting some%0A * (can be none) of the characters without disturbing the relative positions of the remaining%0A * characters. (ie, %22ACE%22 is a subsequence of %22ABCDE%22 while %22AEC%22 is not).%0A *%0A * Here is an example: S = %22rabbbit%22, T = %22rabbit%22 Return 3.%0A */%0A%0A
 publ
@@ -49,16 +49,18 @@
  _115 %7B%0A
+  
   public
@@ -85,24 +85,28 @@
 tion1 %7B%0A    
+  
+  
 public int n
@@ -140,24 +140,30 @@
  t) %7B%0A      
+   
+   
 int m = s.le
@@ -172,24 +172,30 @@
 th();%0A      
+   
+   
 int n = t.le
@@ -208,16 +208,22 @@
 ;%0A      
+  
+    
 int%5B%5D%5B%5D 
@@ -251,16 +251,22 @@
  + 1%5D;%0A%0A
+      
       ch
@@ -291,24 +291,30 @@
 harArray();%0A
+      
       char%5B%5D
@@ -338,32 +338,38 @@
 Array();%0A%0A      
+    
+  
 for (int i = 0; 
@@ -375,32 +375,40 @@
  i %3C= m; i++) %7B%0A
+        
         dp%5Bi%5D%5B0%5D
@@ -411,35 +411,47 @@
 %5D%5B0%5D = 1;%0A      
-%7D%0A%0A
+      %7D%0A%0A      
       for (int j
@@ -463,32 +463,40 @@
  j %3C= n; j++) %7B%0A
+        
         dp%5B0%5D%5Bj%5D
@@ -503,27 +503,39 @@
  = 0;%0A      
-%7D%0A%0A
+      %7D%0A%0A      
       for (i
@@ -551,32 +551,40 @@
  i %3C= m; i++) %7B%0A
+        
         for (int
@@ -598,32 +598,42 @@
  j %3C= n; j++) %7B%0A
+          
           if (sc
@@ -666,32 +666,44 @@
 ) %7B%0A            
+          
+  
 dp%5Bi%5D%5Bj%5D = dp%5Bi 
@@ -730,16 +730,26 @@
 j - 1%5D;%0A
+          
         
@@ -763,32 +763,44 @@
 e %7B%0A            
+        
+    
 dp%5Bi%5D%5Bj%5D = dp%5Bi 
@@ -822,34 +822,64 @@
     
-%7D%0A        %7D%0A      %7D%0A
+          %7D%0A                %7D%0A            %7D%0A  
       
+    
 retu
@@ -895,16 +895,22 @@
 n%5D;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 115