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
dp[i][j]is the number of ways to formt[0..j-1]froms[0..i-1].- If
s[i-1] == t[j-1], that character can be used (contributingdp[i-1][j-1]) or skipped (contributingdp[i-1][j]). - If they differ, the only option is to skip
s[i-1], contributingdp[i-1][j]. - The base cases are
dp[i][0] = 1(the empty target) anddp[0][j] = 0forj > 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.