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

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 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 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