Hard

题目描述

给定一个字符串 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", "aa", "ba", 和 "aba"。

示例 3：

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

提示：

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

解题思路

这道题要求计算字符串的不同子序列个数，是一个经典的动态规划问题。

核心思路： 我们用 dp[i] 表示前 i 个字符能够形成的不同子序列个数。当我们考虑第 i 个字符 s[i-1] 时：

  1. 不选择这个字符：子序列个数仍为 dp[i-1]
  2. 选择这个字符：可以将它添加到前面所有子序列的末尾，得到 dp[i-1] 个新的子序列

因此 dp[i] = 2 * dp[i-1]。

但是这样会产生重复计算。如果字符 s[i-1] 之前出现过，比如在位置 j，那么通过将 s[i-1] 添加到前 j 个字符形成的子序列末尾得到的结果，与之前已经计算过的重复了。

去重策略： 我们用 last[c] 记录字符 c 上次出现时的 dp 值。当遇到重复字符时，需要减去上次的贡献 last[c]。

转移方程变为：dp[i] = 2 * dp[i-1] - last[s[i-1]]

代码实现

class Solution {
public:
    int distinctSubseqII(string s) {
        const int MOD = 1e9 + 7;
        int n = s.length();
        vector<int> last(26, 0);
        long long dp = 1; // 空序列
        
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            long long prev = dp;
            dp = (2 * dp - last[c] + MOD) % MOD;
            last[c] = prev;
        }
        
        return (dp - 1 + MOD) % MOD; // 减去空序列
    }
};

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        last = {}
        dp = 1  # 空序列
        
        for c in s:
            prev = dp
            dp = (2 * dp - last.get(c, 0)) % MOD
            last[c] = prev
            
        return (dp - 1) % MOD  # 减去空序列

public class Solution {
    public int DistinctSubseqII(string s) {
        const int MOD = 1000000007;
        int[] last = new int[26];
        long dp = 1; // 空序列
        
        foreach (char c in s) {
            int idx = c - 'a';
            long prev = dp;
            dp = (2 * dp - last[idx] + MOD) % MOD;
            last[idx] = (int)prev;
        }
        
        return (int)((dp - 1 + MOD) % MOD); // 减去空序列
    }
}

var distinctSubseqII = function(s) {
    const MOD = 1e9 + 7;
    const last = new Array(26).fill(0);
    let dp = 1; // 空序列
    
    for (let c of s) {
        const idx = c.charCodeAt(0) - 97; // 'a'.charCodeAt(0)
        const prev = dp;
        dp = (2 * dp - last[idx] + MOD) % MOD;
        last[idx] = prev;
    }
    
    return (dp - 1 + MOD) % MOD; // 减去空序列
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。我们只需要遍历一次字符串，并使用固定大小的数组记录每个字符的上次贡献值。

相关题目