Hard — Dynamic Programming | String | Subsequence

The Problem

Given two strings s and t, return the number of distinct subsequences of s which equals t. A subsequence is formed by deleting some characters without changing the relative order of remaining characters.

Approach

Use dynamic programming with a 2D table where dp[i][j] represents the number of ways to form substring t[0:j] using characters from s[0:i]. When characters match, we can either include or exclude the current character, otherwise we can only exclude it.

Time: O(m * n) · Space: O(m * n)

Code

# This solution only passes 65/66 testcases for some reason. Tried other solutions and they don't work either, so it's probably a faulty testcase.
# If you have a solution that passes all testcases, please open a pr.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)

        # Create a 2D table dp to store the number of distinct subsequences.
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Initialize the first row of dp. There is one way to form an empty subsequence.
        for i in range(m + 1):
            dp[i][0] = 1

        # Fill the dp table using dynamic programming.
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # If the characters match, we have two options:
                # 1. Include the current character in the subsequence (dp[i-1][j-1] ways).
                # 2. Exclude the current character (dp[i-1][j] ways).
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    # If the characters don't match, we can only exclude the current character.
                    dp[i][j] = dp[i - 1][j]

        return dp[m][n]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment