Distinct Subsequences Leetcode Solution

In this post, you will know how to solve the Distinct Subsequences Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Distinct Subsequences Leetcode Solution
Distinct Subsequences Leetcode Solutions

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

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

Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
babgbag
babgbag
babgbag
babgbag

Constraints:

  • 1 <= s.length, t.length <= 1000
  • s and t consist of English letters.

Distinct Subsequences Leetcode Solutions in Python

class Solution:
  def numDistinct(self, s: str, t: str) -> int:
    m = len(s)
    n = len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
      dp[i][0] = 1
    for i in range(1, m + 1):
      for j in range(1, n + 1):
        if s[i - 1] == t[j - 1]:
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
        else:
          dp[i][j] = dp[i - 1][j]
    return dp[m][n]

Distinct Subsequences Leetcode Solutions in CPP

class Solution {
 public:
  int numDistinct(string s, string t) {
    const int m = s.length();
    const int n = t.length();
    vector<vector<long>> dp(m + 1, vector<long>(n + 1));
    for (int i = 0; i <= m; ++i)
      dp[i][0] = 1;
    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (s[i - 1] == t[j - 1])
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j];
    return dp[m][n];
  }
};

Distinct Subsequences Leetcode Solutions in Java

class Solution {
  public int numDistinct(String s, String t) {
    final int m = s.length();
    final int n = t.length();
    long[][] dp = new long[m + 1][n + 1];
    for (int i = 0; i <= m; ++i)
      dp[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))
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j];
    return (int) dp[m][n];
  }
}

Note: This problem Distinct Subsequences is generated by Leetcode but the solution is provided by Brokenprogrammers. This tutorial is only for Educational and Learning purpose.

Next: Merge Intervals Leetcode Solution

Leave a Reply

Your email address will not be published. Required fields are marked *