LeetCode 115: Distinct Subsequences (2D DP Prefix Matching)

2026-03-18 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 115Dynamic ProgrammingString

Today we solve LeetCode 115 - Distinct Subsequences.

Source: https://leetcode.com/problems/distinct-subsequences/

LeetCode 115 Distinct Subsequences DP transition diagram

English

Problem Summary

Given strings s and t, return how many distinct subsequences of s equal t.

Key Insight

Use prefix DP. Let dp[i][j] be the number of ways to form t[0..j-1] from s[0..i-1]. For each new character in s, we either skip it or use it when characters match.

Brute Force and Limitations

Backtracking over keep/skip decisions explores 2^|s| branches and times out quickly. DP compresses repeated subproblems into polynomial time.

Optimal Algorithm Steps (2D DP)

1) Initialize dp[i][0] = 1 for all i (empty t can always be formed).
2) Initialize dp[0][j] = 0 for j > 0 (non-empty t cannot come from empty s).
3) Transition: dp[i][j] = dp[i-1][j]; if s[i-1] == t[j-1], add dp[i-1][j-1].
4) Answer is dp[m][n].

Complexity Analysis

Time: O(mn), where m = |s|, n = |t|.
Space: O(mn) for full table (can be optimized to O(n) with reverse iteration).

Common Pitfalls

- Forgetting dp[i][0] = 1 base case.
- Using 32-bit int in languages where count may overflow (use long/long long where needed).
- Iterating 1D optimization left-to-right and corrupting states.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), 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++) {
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return (int) dp[m][n];
    }
}

func numDistinct(s string, t string) int {
    m, n := len(s), len(t)
    dp := make([][]int64, m+1)
    for i := range dp {
        dp[i] = make([]int64, n+1)
        dp[i][0] = 1
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            dp[i][j] = dp[i-1][j]
            if s[i-1] == t[j-1] {
                dp[i][j] += dp[i-1][j-1]
            }
        }
    }

    return int(dp[m][n])
}

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
        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++) {
                dp[i][j] = dp[i - 1][j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return (int)dp[m][n];
    }
};

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

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j]
                if s[i - 1] == t[j - 1]:
                    dp[i][j] += dp[i - 1][j - 1]

        return dp[m][n]

var numDistinct = function(s, t) {
  const m = s.length, n = t.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = 1;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j];
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] += dp[i - 1][j - 1];
      }
    }
  }

  return dp[m][n];
};

中文

题目概述

给定字符串 s 和 t，返回 s 的不同子序列中，等于 t 的个数。

核心思路

定义前缀 DP：dp[i][j] 表示用 s 前 i 个字符组成 t 前 j 个字符的方案数。每个新字符要么不用（继承上方），要么在匹配时使用（加左上）。

基线解法与不足

回溯会对每个字符做“选/不选”分支，复杂度接近 O(2^m)，在长字符串下不可行。DP 可以把重叠子问题收敛为 O(mn)。

最优算法步骤（二维 DP）

1）初始化 dp[i][0] = 1（任意前缀都能组成空串）。
2）初始化 dp[0][j] = 0（空串无法组成非空目标）。
3）状态转移：先令 dp[i][j] = dp[i-1][j]；若 s[i-1] == t[j-1]，再加上 dp[i-1][j-1]。
4）答案为 dp[m][n]。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(mn)（可用一维数组优化到 O(n)）。

常见陷阱

- 忘记设置 dp[i][0] = 1。
- 计数可能较大，部分语言应使用 long/long long。
- 做一维优化时从左到右更新，导致状态被提前覆盖。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), 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++) {
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return (int) dp[m][n];
    }
}

func numDistinct(s string, t string) int {
    m, n := len(s), len(t)
    dp := make([][]int64, m+1)
    for i := range dp {
        dp[i] = make([]int64, n+1)
        dp[i][0] = 1
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            dp[i][j] = dp[i-1][j]
            if s[i-1] == t[j-1] {
                dp[i][j] += dp[i-1][j-1]
            }
        }
    }

    return int(dp[m][n])
}

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
        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++) {
                dp[i][j] = dp[i - 1][j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return (int)dp[m][n];
    }
};

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

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j]
                if s[i - 1] == t[j - 1]:
                    dp[i][j] += dp[i - 1][j - 1]

        return dp[m][n]

var numDistinct = function(s, t) {
  const m = s.length, n = t.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = 1;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j];
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] += dp[i - 1][j - 1];
      }
    }
  }

  return dp[m][n];
};