Q-32 Distinct Subsequences - LeetCode 115

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length() , n = t.length();
        // return solve(s, t, m , n, new Integer[m+1][n+1]);

        //tabulization
        /* as base case of recursion logice are goint <0 ,we will make tabulization for 
        dp[m+1][n+1] and handle base cases on i==0 || j==0 . 
        making dp 1 based indexing we have to take characters out of string by i-1 , j-1
        */

        int dp[][] = new int[m+1][n+1];

        //base case
        for(int i = 0;i < m+1 ; i++)dp[i][0] = 1;
        for(int j = 1;j < n+1 ; j++)dp[0][j] = 0;

        for(int i = 1 ; i < m+1 ; i++){
            for(int j = 1 ;j < n+1 ; j++){
                
                char ch1 = s.charAt(i-1) , ch2 = t.charAt(j-1);

                //if chars are matching find answer in rest of the strings and also 
                //find answers in rest of the string 's' keeping for same character in 't'
                if(ch1 == ch2)
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

                //if chars are not matching find answer in rest of the strings
                else
                dp[i][j] =  dp[i-1][j];
    
            }
        }

        return dp[m][n];
    }

    //we are matching all characters in t to s
    //Recursion-> 2^n * 2^m Memo-> n*m | sc- n+m (height of stack) + n*m(dp)

    //changing into 1 based indexing to handle tabulization base case better
    public int solve(String s , String t , int i , int j , Integer[][] dp){
        if(j == 0 )  //if all characters are matched
        return 1;
        if(i == 0)   //if characters remains to be matched, but 's' is exhausted
        return 0;
        
        if(dp[i][j] != null)
        return dp[i][j];

        char ch1 = s.charAt(i-1) , ch2 = t.charAt(j-1);

        //if chars are matching find answer in rest of the strings and also 
        //find answers in rest of the string 's' keeping for same character in 't'
        if(ch1 == ch2)
        return dp[i][j] = solve(s,t,i-1,j-1 , dp) + solve(s,t,i-1,j ,dp);

        //if chars are not matching find answer in rest of the strings
        else
        return dp[i][j] =  solve(s,t,i-1,j , dp);
    }
}