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).

 

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n²) time and O(n) memory.

O(n²) memory is also acceptable if you do not know how to optimize memory.

 

 

public class Solution {    /**     * @param S, T: Two string.     * @return: Count the number of distinct subsequences     */    public int numDistinct(String S, String T) {        // write your code here        if(T.length()==0) return 1;        if(S.length()==0) return 0;        int m=S.length();        int n=T.length();                int[][] res=new int[m+1][n+1];                for(int i=0;i<=m;i++)        {            res[i][0]=1;        }                for(int i=1;i<=m;i++)        {            for(int j=1;j<=n;j++)            {                if(S.charAt(i-1)==T.charAt(j-1))                {                    res[i][j]=res[i-1][j-1]+res[i-1][j];                }                else                {                    res[i][j]=res[i-1][j];                }            }        }                return res[m][n];            }}