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); } }