0115 Distinct Subsequences

0115 Distinct Subsequences#

Problem#

Given two strings s and t, return the number of distinct subsequences of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Examples#

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

### Constraint
```text
1 <= s.length, t.length <= 1000
s and t consist of English letters.

Analysis#

This could be a permutation/arrangement problem.

How many ways to make s (balls) into t (baskets)?

Solution#

This is a complete problem, which can be solved by:

  • Backtracking

  • Dynamic Programming

  • dp[i,j]: the number of ways to generate t[j:] from s[i:]

  • state: i, j

  • choices:

  • state transition:

    • if s[i] != t[j]: the first character is the not same

      • only one choice, which is we cannot put s[i] in the bag

        • dp[i,j] = dp[i+1, j]

    • if s[i] == t[j]:

      • there are two choices: put s[i] in the bag, or not

        • dp[i,j] = dp[i+1,j+1] + dp[i+1, j]

  • base case:

    • j=len(t), where t[j:] is empty. this always one way, which is not do anything.

    • s shorter than t: return 0

# DP Function
def distinctSubsequences(s,t):

    # dp(i,j) return the number of distinct subsequences of t[j:] in s[i:]
    def dp(i, j):
        # base case 1
        if j == len(t):
            return 1
        # base case 2
        if len(s[i:]) < len(t[j:]):
            return 0
        # if the current characters do not match
        if s[i] != t[j]:
            return dp(i+1, j)
        else:
            return dp(i+1, j+1) + dp(i+1,j)
    
    return dp(0,0)

# test case
# 3
s = "rabbbit"
t = "rabbit"
print(distinctSubsequences(s,t))
# 5
s = "babgbag"
t = "bag"
print(distinctSubsequences(s,t))

3
5

# DP Function with memo
def distinctSubsequences(s,t):
    memo = {}

    # dp(i,j) return the number of distinct subsequences of t[j:] in s[i:]
    def dp(i, j):
        # base case 1
        if j == len(t):
            return 1
        # base case 2
        if len(s[i:]) < len(t[j:]):
            return 0
        
        if (i,j) in memo:
            return memo[(i,j)]
        # if the current characters do not match
        if s[i] != t[j]:
            memo[(i, j)] = dp(i+1, j)
        else:
            memo[(i,j)] = dp(i+1, j+1) + dp(i+1,j)
        return memo[(i,j)]
        
    return dp(0,0)

# test case
# 3
s = "rabbbit"
t = "rabbit"
print(distinctSubsequences(s,t))
# 5
s = "babgbag"
t = "bag"
print(distinctSubsequences(s,t))

3
5

# DP table
def distinctSubsequences(s,t):
    m, n = len(s), len(t)
    dp = [[0] * (n+1) for _ in range(m+1)]

    # base case
    for i in range(m+1):
        dp[i][n] = 1
    for j in range(n):
        dp[m][j] = 0
    
    for i in range(m-1,-1,-1):
        for j in range(n-1, -1, -1):
            if s[i] != t[j]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
    return dp[0][0]

# test case
# 3
s = "rabbbit"
t = "rabbit"
print(distinctSubsequences(s,t))
# 5
s = "babgbag"
t = "bag"
print(distinctSubsequences(s,t))

3
5
Contents