Distinct Subsequences

 1 public class Solution {
 2     public int numDistinct(String S, String T) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         if(S == null || S.length() == 0){
 6             return 0;
 7         }
 8         
 9         if(T == null || T.length() == 0){
10             return 1;
11         }
12         
13         int sLen = S.length(), tLen = T.length();
14         if(sLen < tLen){
15             return 0;
16         }
17         
18         int[][] dp = new int[sLen + 1][tLen + 1];
19         for(int i = 0; i < sLen + 1; i++){
20             dp[i][0] = 1;
21         }
22         
23         for(int i = 1; i < tLen + 1; i++){
24             dp[0][i] = 0;
25         }
26         
27         for(int i = 1; i < sLen + 1; i++){
28             for(int j = 1; j < tLen + 1; j++){
29                 if(S.charAt(i - 1) == T.charAt(j - 1)){
30                     dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
31                 } else {
32                     dp[i][j] = dp[i - 1][j];
33                 }
34             }
35         }
36         
37         return dp[sLen][tLen];
38         
39     }
40 }