Given two strings s and t, return the number of distinct subsequences of s which equals t.
A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S. rabbbit rabbbit rabbbit class Solution { public int numDistinct(String s, String t) { // we will use little bit of backtracking here int dp[][] = new int[s.length()][t.length()]; for(int row[] : dp) Arrays.fill(row, -1); return distinctCount(s,t,s.length()-1,t.length()-1,dp); } public int distinctCount(String s, String t, int i,int j,int dp[][]){ //base case if(i=0 && j=0 && s.charAt(i)==t.charAt(j)) return 1; if(j<0) return 1; if(i<0) return 0; if(dp[i][j]!=-1) return dp[i][j]; if(s.charAt(i)==t.charAt(j)){ // so basically if its a, match , we will either reduce s and t index both or we will just reduce the index of s only. // in both the case we will return the sum of values that we get. return dp[i][j]= distinctCount(s,t,i-1,j-1,dp) + distinctCount(s,t,i-1,j,dp); } else{ // else if its not a match we will have to reduce the s string index so //as to reach to an index of s where s.charAt(i) == t.charAt(j); return dp[i][j] = distinctCount(s,t,i-1,j,dp); } } } 
Top comments (0)