题目

给定一个字符串 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 仅由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/distinct-subsequences-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

没有思路，学习一下，官解讲的很清楚，O(n)时间，见「这里」。

代码

  1. class Solution {
  2.     public int distinctSubseqII(String s) {
  3.         int mod = (int) (1e9 + 7);
  4.         int n = s.length();
  5.         long[] dp = new long[n + 1];
  6.         dp[0] = 1;
  7.         int[] last = new int[26];
  8.         for (int i = 1; i <= n; i++) {
  9.             int index = s.charAt(i - 1) - 'a';
  10.             dp[i] = 2 * dp[i - 1] % mod;
  11.             if (last[index] > 0) {
  12.                 // 可能减成负的，也要取余
  13.                 dp[i] = (dp[i] - dp[last[index] - 1] + mod) % mod;
  14.             }
  15.             // 这里last中的值从1开始，省去了初始化-1
  16.             last[index] = i;
  17.         }
  18.         return (int) (dp[n] - 1);
  19.     }
  20. }