940. 不同的子序列 II

短命女 2024-04-03 13:05 15阅读 0赞

### 940. 不同的子序列 II ###

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

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

> 例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是。

思路：

1.  先思考一个不同字母字符串的所有子序列。 如 “abc"  
    陆续以不同的字符作为子序列的结尾，从左到右可得

> 遍历到a 子序列： a  
> 遍历到b 子序列：a ab b  
> 遍历到c 子序列：a ab b ac abc bc c

很明显可以看出，**dp\[i\] = dp\[i-1\] + new + 1**  
new即是上一个所有的子字符串后面加上这个新的字母，1即是自己本身这个新增的字母

1.  那现在思考如果该字符串有重复的字母。  
    重复的字母就意味着会出现重复的子序列，根据上面可很容易想到，在最新的dp\[i\]中，只有new和1(自己)是可能存在重复的子序列的。如"abaa"

> 遍历到第一个a 子序列： a  
> 遍历到第一个b 子序列：a + ab + b  
> 遍历到第二个a 子序列：a ab b + aa aba ba + a 其中new中  
> 遍历到第三个a 子序列：a ab b aa aba ba + aa aba ba aaa abaa baa + a

可以看出来，

> 第一个a：新增了子序列为a,重复子序列无  
> 第二个a：新增子序列 aa aba ba a,重复子序列为a  
> 第三个a：新增子序列 aa aba ba aaa abaa baa a ,重复子序列为aa aba ba a

很明显，如果你遍历到了第三个a，new会把前面所有的子序列后都加个a，而这其中重复的都是第二个a中新增的子序列。  
很好理解，因为当遍历到第三个a时，肯定已经拥有了当遍历到第二个a时的所有子序列，new是把这些子序列尾部加a，就相当于把它做过的事情再做一遍，这一部分必定是重复的。  
同时，你自己本身字母作为子序列也是重复的

**dp\[i\] = dp\[i-1\] + new + 1 - repeat**  
其中new即是dp\[i-1\]的子序列后尾部新增最新字母，两个数值一样

所以要初始化一个长度为26的int数组，用于存放每个字母的repeat子序列，也就是每个字母的新增子序列。也就是new + 1。

class Solution {
        
        public int distinctSubseqII(String s) {
        
    
            int[] repeatArr = new int[26];
    
            char[] arr = s.toCharArray();
    
            // 记录子序列数目
            int count = 0;
    
            int mod = (int)(1e9 + 7);
    
            // 记录重复子序列数目
            int repeat = 0;
    
            // 2.遍历
            for (int i = 0; i < s.length(); i++) {
        
                // repeatCount
                int j = arr[i] - 'a';
                repeat = repeatArr[j];
                // 记录该字母新增的子序列（最新）
                repeatArr[j] = (count+1)%mod;
                count = ((2 * count)%mod - repeat + 1 + mod)%mod;
            }
            return count;
        }
    }

运行结果：  
![在这里插入图片描述][29a5d55c9374488689a5547ef5060fcd.png]

总结：类似问题先举例简单字符串，一步步抽丝剥茧，发现类似规律后一击必杀

[29a5d55c9374488689a5547ef5060fcd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/281745d9fdee444788a05eb313bad249.png