115. Distinct Subsequences Leetcode Java

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:

Dynamic programming.

Assume DP[i][j] represent the number of distinct subsequences that T.substring(0,j) in S.substring(0,i). 

Clearly that 

if(T.charAt(j)==S.charAt(i)): DP[i][j]=DP[i-1][j] + DP[i-1][j-1]. For example using the example in the question. S="rabbbit"; T="rabbit", Assume S.charAt(i) is the 3rd 'b' in S, and T.charAt(j) is the second 'b' in T. Here DP[i-1][j]=1 because "rabb" has 1 distinct subsequences of "rabb", DP[i-1][j-1]=2, because "rabb" has 2 distinct subsequences of "rab", so DP[i][j]=2+1=3. All the valid distinct subsequences DP[i-1][j-1] + T.charAt(j) will be distinct subsequence of S.charAt(0,i).All the distinct subsequence DP[i-1][j] will be still the distinct subsequences. They are distinct from each other because one of them(DP[i-1][j]) doesn't use S.charAt(i), while the other one(DP[i-1][j-1]) must use S.charAt(i).

if(T.charAt(j)!=S.charAt(i)) DP[i][j]=DP[i-1][j]. 

According to the recursion equation, to calculate DP[i][j], all we need is (i-1)th information, so if we want save some space and use 1-d array as the DP array, we can iterate the j from end to start to avoid replacing DP[i-1][j-1] with DP[i][j-1]. Here assume there is an empty char before S and before J. So DP[0][0]=1; DP[0][j]=0 (j!=0); DP[i][0]=1; By doing so, we can avoid take special care of the first char at index 0.
Time complexity: O(m*n) O(n) extra space

 public int numDistinct(String S, String T) {  
    if(S==null || T==null || T.length()> S.length()) return 0;  
    int[] res=new int[T.length()+1];  
    res[0]=1;  
    for(int i=1;i<=S.length();i++){  
      for(int j=T.length();j>=1;j--){  
        if(S.charAt(i-1)==T.charAt(j-1)) res[j]+=res[j-1];  
      }  
    }  
    return res[T.length()];  
   }