⚡Flashcard Drill➔
NeetCode #732LC-115Hard2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems

#732 · #115 · Distinct Subsequences(不同的子序列)

📌 Problem Statement & Constraints

Given strings s and t, return the number of distinct subsequences of s that equal t. The answer fits in a signed 32-bit integer. Constraints: 1 <= s.length, t.length <= 1000, lowercase English letters.

💡 Core Algorithmic Approaches

  1. dp[i][j] is the number of ways to form t[0..j-1] from s[0..i-1].
  2. If s[i-1] == t[j-1], that character can be used (contributing dp[i-1][j-1]) or skipped (contributing dp[i-1][j]).
  3. If they differ, the only option is to skip s[i-1], contributing dp[i-1][j].
  4. The base cases are dp[i][0] = 1 (the empty target) and dp[0][j] = 0 for j > 0.

💻 Benchmark Python3 Implementation

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = 1               # the empty target has one match
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j]              # skip s[i-1]
                if s[i - 1] == t[j - 1]:
                    dp[i][j] += dp[i - 1][j - 1]     # or use it
        return dp[m][n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): one state per pair of prefixes.
💾 Space Complexity
O(m * n), reducible to O(n).

⚠️ Interview Pitfalls & Follow-ups

  • Adding dp[i-1][j-1] unconditionally: the use-it term applies only when the characters match.
  • Forgetting dp[i][0] = 1: matching the empty target always has exactly one way.
  • Setting dp[0][j] = 1: with an empty source, no non-empty target can be matched.
  • Treating subsequences as substrings: the chosen characters need not be contiguous.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems