困难

问题描述

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

• 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

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

动态规划

将 $26$ 个字母映射到 $0 - 26$，假设 $dp[i]$ 为以序号$i$ 结尾的子字符串的个数，然后考虑状态转移，当字符串后增加一个字母时，这个新增的字符串必然是不重复的，而增加字母前的子字符串的最后一位必然是空字符串或者是 $26$ 个字母的一位，因此，可得到状态转移方程：

$$dp[i] = \sum_{k=0}^{25} dp[k] + 1$$

根据此方法统计必然不包含重复字符串，因此，最后将以各个字母结尾的子字符串个数累加即为答案。

/**
 * @param {string} s
 * @return {number}
 */
var distinctSubseqII = function (s) {
  const MOD = Math.pow(10, 9) + 7
  const dp = new Array(26).fill(0)
  for (const c of s) {
    const code = c.charCodeAt(0) - 97
    let total = 1
    for (let i = 0; i < 26; i++) {
      total = (total + dp[i]) % MOD
    }
    dp[code] = total
  }
  return dp.reduce((s, c) => (s + c) % MOD, 0)
}

• 时间复杂度：$O(Cn)$，其中 $C$ 为 26
• 空间复杂度：$O(C)$，其中 $C$ 为 26