Skip to content

115. Distinct Subsequences 👍

Approach 1: 2D DP

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int numDistinct(string s, string t) {
    const int m = s.length();
    const int n = t.length();
    vector<vector<unsigned long>> dp(m + 1, vector<unsigned long>(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)
        if (s[i - 1] == t[j - 1])
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j];

    return dp[m][n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int numDistinct(String s, String t) {
    final int m = s.length();
    final int 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)
        if (s.charAt(i - 1) == t.charAt(j - 1))
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j];

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def numDistinct(self, s: str, t: str) -> int:
    m = len(s)
    n = 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):
        if s[i - 1] == t[j - 1]:
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
        else:
          dp[i][j] = dp[i - 1][j]

    return dp[m][n]

Approach 2: 1D DP

  • Time: $O(mn)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int numDistinct(string s, string t) {
    const int m = s.length();
    const int n = t.length();
    vector<unsigned long> dp(n + 1);
    dp[0] = 1;

    for (int i = 1; i <= m; ++i)
      for (int j = n; j >= 1; --j)
        if (s[i - 1] == t[j - 1])
          dp[j] += dp[j - 1];

    return dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int numDistinct(String s, String t) {
    final int m = s.length();
    final int n = t.length();
    long[] dp = new long[n + 1];
    dp[0] = 1;

    for (int i = 1; i <= m; ++i)
      for (int j = n; j >= 1; --j)
        if (s.charAt(i - 1) == t.charAt(j - 1))
          dp[j] += dp[j - 1];

    return (int) dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def numDistinct(self, s: str, t: str) -> int:
    m = len(s)
    n = len(t)
    dp = [1] + [0] * n

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

    return dp[n]