940.不同的子序列 II

不同的子序列 II

给定一个字符串 s，返回 s 的不同非空子序列的个数。

由于答案可能很大，请返回答案模 10^9 + 7。

示例 1:

输入：s = “abc”
输出：7

示例 2:

输入：s = “aba”
输出：6

提示:

• 1 <= s.length <= 2000
• s 由小写英文字母组成

解析

使用动态规划，dp[i] 表示以 s[i] 结尾的不同子序列个数。维护每个字符最后出现的位置。

var distinctSubseqII = function (s) {
  const MOD = 10 ** 9 + 7;
  const last = new Array(26).fill(-1);
  const dp = new Array(s.length).fill(0);

  for (let i = 0; i < s.length; i++) {
    let sum = 1;
    for (let j = 0; j < 26; j++) {
      if (last[j] !== -1) {
        sum = (sum + dp[last[j]]) % MOD;
      }
    }
    dp[i] = sum;
    last[s.charCodeAt(i) - 97] = i;
  }

  let result = 0;
  for (let i = 0; i < s.length; i++) {
    result = (result + dp[i]) % MOD;
  }

  return result;
};

时间复杂度 O(n * 26)，空间复杂度 O(n)。