Leetcode Distinct Subsequences problem solution

YASH PAL,

In this Leetcode Distinct Subsequences problem solution we have 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). It is guaranteed the answer fits on a 32-bit signed integer.

Leetcode Distinct Subsequences problem solution

Problem solution in Python.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [1] * (len(s) + 1)
        for r, t_char in enumerate(t, 1):
            prev, dp[0] = dp[0], 0
            for c, s_char in enumerate(s, 1):
                curr = dp[c]
                dp[c] = dp[c-1] + (t_char == s_char and prev)
                prev = curr
        return dp[-1]

Problem solution in Java.

public int numDistinct(String s, String t) {
        
        int[] dp = new int[t.length()+1];
        dp[0] = 1;
        
        for(int i=1;i<=s.length();i++) {
            int min = Math.min(i, t.length());
            for(int j=min;j>=1;j--) {
                if(s.charAt(i-1) == t.charAt(j-1)) {
                    dp[j] += dp[j-1];
                }
            }
        }
        
        return dp[t.length()];
    }

Problem solution in C++.

class Solution {
public:
int numDistinct(string s, string t)
{
int n = t.size(), m = s.size();

    if(n>m)return 0;
    
    vector<vector<unsigned int>> dp(n,vector<unsigned int>(m,0));
    
    for(int x=0; x<m; x++)
    {
        if(t[0] == s[x])
        {
            dp[0][x] = dp[0][max(x-1,0)]+1;
        }
        else
        {
            dp[0][x] = dp[0][max(x-1,0)];
        }
    }
    
    for(int x=1; x<n; x++)
    {
        for(int y=x; y<m; y++)
        {
            if(t[x] == s[y])
            {
           
                    
                dp[x][y] = dp[x-1][y-1]+dp[x][y-1];
            }
            else
            {
                dp[x][y] = dp[x][y-1];
            }
        }
    }

    
    return dp[n-1][m-1];
    
}
};

Problem solution in C.

int numDistinct(char* s, char* t) {
	int len1, len2;
	if((len1 = strlen(s)) == 0 || (len2 = strlen(t)) == 0){
		return 0;
	}

	int dp[len2], i, j;
	int cur = 0;
	memset(dp, 0, sizeof(int) * len2);

	for(i = 0; i < len1; ++i){
		if(cur != len2){
			if(cur == 0){
				if(s[i] == t[cur]){
					dp[cur++] = 1;
				}
				continue;
			}

			for(j = cur; j > -1; --j){
				if(t[j] == s[i]){
				    if(j == 0){
				        dp[j] = dp[j] + 1;
				        continue;
				    }
					dp[j] = dp[j] + 1 * dp[j-1];
					if(j == cur){
						cur++;
					}
				}
			}
		}
		else{
			for(j = cur - 1; j > -1; --j){
				if(t[j] == s[i]){
				    if(j == 0){
				        dp[j] = dp[j] + 1;
				        continue;
				    }
					dp[j] = dp[j] + 1 * dp[j-1];
				}
			}
		}
	}

	return dp[len2-1];
}

coding problems solutions