LeetCode_动态规划_困难_940.不同的子序列 II

╰半橙微兮° 2023-10-07 20:17 36阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个字符串 s，计算 s 的不同非空子序列的个数。因为结果可能很大，所以返回答案需要对 109 \+ 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

## 2.思路 ##

（1）回溯算法  
如果使用回溯算法，那么本题就与[LeetCode\_回溯\_中等\_78.子集][LeetCode_78.]这题十分相似，只不过多了一个去重的操作，这里可以选择用 hashSet 来记录不同的非空子序列。但是由于本题 s 的长度最高可达 2000，所以在 LeetCode 中提交时会出现“超出时间限制”的提示！

（2）动态规划  
思路参考[本题官方题解][Link 1]。

① 定义 dp 数组，**dp\[i\] 表示 s 中以某个小写字母结尾的不同非空子序列个数**。

/*
    	dp[0] 表示 s 中以小写字母 a 结尾的不同非空子序列个数
    	dp[1] 表示 s 中以小写字母 b 结尾的不同非空子序列个数
    	...
    	dp[25] 表示 s 中以小写字母 z 结尾的不同非空子序列个数
    	它们的初始值均为 0
    */
    long[] dp = new long[26];

② 定义变量 res，用于记录不同非空子序列的个数，其初始值为 0。

③ 遍历字符串 s，记当前的小写字母为 letter = s.charAt(i)，然后再做如下处理：  
1）记 letterCnt 表示 s\[0…i - 1\] 中以 letter 结尾的不同非空子序列个数，如果 i = 0，那么 letterCnt 为默认值 0；

long letterCnt = dp[letter - 'a'];

2）算上当前的 letter，那么 s\[0…i\] 中以 letter 结尾的子序列个数 dp\[letter - ‘a’\] = res + 1；

/*
    	(1) 更新 dp[letter - 'a']，让其表示 s[0...i] 中以 letter 结尾的子序列个数
    	(2) 此处的 res 表示的还是 s[0...i - 1] 中不同非空子序列的个数
    	(3) dp[letter - 'a'] = res + 1 的说明：
    		如果我们已知 s[0...i - 1] 中不同非空子序列的个数为 res，那么要求 s[0...i] 中以 s[i] = letter 结尾的子序列时
    		可以直接将 res 个子序列的末尾都拼接上字母 letter，并且同时还考虑以 letter 自身一个字母所表示的子序列，所以就可
    		以推出 dp[letter - 'a'] = res + 1
    */
    dp[letter - 'a'] = res + 1;

3）更新 res；

/*
    	(1) 在更新 res 之前，res 表示 s[0...i - 1] 中不同非空子序列的个数；
    	(2) 此时要求出 s[0...i] 中不同非空子序列的个数，并且已知 
    		- 第 i 个小写字母 s[i] = letter
    		- s[0...i - 1] 中以 letter 结尾的不同非空子序列个数 letterCnt
    	(3) res += (res + 1 - letterCnt) % MOD_NUM 的说明如下：
    		- 首先，如果不排除重复的子序列，那么 res = res + res + 1，此处的推导与上面的 dp[letter - 'a'] = res + 1 类似，只不过
    		  这里的更新后的 res 是包含更新前的 res 的，所以需要进行累加。
    		- 然后，我们再考虑去重的问题，此时我们需要思考，从 res 变为 res + res + 1 的过程中，有哪些子序列是重复的？
    		  例如，s[0...2] = "bac"，s[0...3] = "bacc"
    		  s[0...2] 中不同非空子序列 = {b, a, c, ba, bc, ac, bac}，res -> res + res + 1 后
    		  s[0...3] 中非空子序列 = {b, a, c, ba, bc, ac, bac, bc, ac, cc, bac, bcc, acc, bacc, c}
    		  显然我们可以发现重复的子序列 = {c, bc, ac, bac}，而它们正好是 s[0...2] 中以 letter(即小写字母 c) 结尾的不同非空子序列！
    		- 其实，这一点也比较容易理解，假设 s[0...i - 1] 中的某个以 letter 结尾的子序列 bac，那么去掉 c 后的 ba 一定也是 s[0...i - 1]
    		  的子序列，经过 res -> res + res + 1 后，一定会生成子序列 ba + c = bac，这样便与之前存在的 bac 重复了，所以 res + res + 1
    		  还需要减去 letterCnt。
    */
    res += (res + 1 - letterCnt) % MOD_NUM;

## 3.代码实现（Java） ##

//思路1————回溯算法
    class Solution {
        
        int MOD_NUM = 1000000007;
        // res 记录不同非空子序列的个数，其初始值为 0
        int res = 0;
        // hashSet 记录所有的非空子序列
        Set<String> hashSet = new HashSet<>();
        // builder 记录当前的非空子序列
        StringBuilder builder = new StringBuilder();
        
        public int distinctSubseqII(String s) {
        
            int length = s.length();
            char[] chs = s.toCharArray();
            backtrace(chs, 0);
            return res;
        }
        
        public void backtrace(char[] chs, int start) {
        
            String curSubString = builder.toString();
            if (!curSubString.equals("") && !hashSet.contains(curSubString)) {
        
                res = (res + 1) % MOD_NUM;
                hashSet.add(curSubString);
            }
            //回溯算法框架
            for (int i = start; i < chs.length; i++) {
        
                //做选择
                builder.append(chs[i]);
                backtrace(chs, i + 1);
                //撤销选择
                builder.deleteCharAt(builder.length() - 1);
            }
        }
    }

//思路2————动态规划
    class Solution {
        
        public int distinctSubseqII(String s) {
        
            long MOD_NUM = 1000000007;
            int length = s.length();
            //dp[i] 表示 s 中以某个小写字母结尾的不同非空子序列个数
            long[] dp = new long[26];
            // res 记录不同非空子序列的个数，初始值为 0
            long res = 0;
            //遍历字符串 s
            for (int i = 0; i < length; i++) {
        
                //当前遍历到的小写字母记为 letter
                char letter = s.charAt(i);
                //letterCnt 表示 s[0...i - 1] 中以 letter 结尾的子序列个数
                long letterCnt = dp[letter - 'a'];
                /*
                    (1) 算上当前的 letter，s[0...i] 中以 letter 结尾的子序列个数 dp[letter - 'a'] = res + 1
                    (2) 此处的 res 表示 s[0...i - 1] 中不同非空子序列的个数
                */
                dp[letter - 'a'] = res + 1;
                //更新 res
                res += (res + 1 - letterCnt) % MOD_NUM;
            }
            return (int)(res % MOD_NUM);
        }
    }

[LeetCode_78.]: https://blog.csdn.net/weixin_43004044/article/details/119963339
[Link 1]: https://leetcode.cn/problems/distinct-subsequences-ii/solution/bu-tong-de-zi-xu-lie-ii-by-leetcode-solu-k2h5/