Distinct Subsequences.java

public class Solution {
    public int numDistinct(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int n=S.length(); 
        int m=T.length(); 
        if(n==0) return 0; 
        int d[][]=new int [n][m];
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                d[i][j]=0; 
                if(S.charAt(i)==T.charAt(j))
                {
                    if(j==0)
                    {
                        d[i][j]+=1; 
                    }else if(i!=0)
                    {
                        d[i][j]+=d[i-1][j-1];
                    }
                }
                if(i!=0) d[i][j]+=d[i-1][j];
            }
        }
        return d[n-1][m-1];
    }
}