Leetcode 115 Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

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.

Solution 1: Use DP, two cases: (1) c[i]==c[j]; (2) c[i]!=c[j];

 public class Solution {  
   public int numDistinct(String s, String t) {  
     int m=s.length();  
     int n=t.length();  
     int[][] dp=new int[m+1][n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (j==0) dp[i][j]=1;  
         else if (i==0) dp[i][j]=0;  
         else if (s.charAt(i-1)==t.charAt(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];  
   }  
 }  

Solution 2: optimize space to O(n)

 public class Solution {  
   public int numDistinct(String s, String t) {  
     int m=s.length();  
     int n=t.length();  
     int[] dp=new int[n+1];  
     for (int i=0; i<=m; i++) {  
       int pre=0;  
       for (int j=0; j<=n; j++) {  
         int temp=dp[j];  
         if (j==0) dp[j]=1;  
         else if (i==0) dp[j]=0;  
         else if (s.charAt(i-1)==t.charAt(j-1)) dp[j]=dp[j]+pre;  
         //else dp[j]=dp[j];  
         pre=temp;  
       }  
     }  
     return dp[n];  
   }  
 }