题目描述

给定一个字符串 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)

示例 1:

输入: S = "rabbbit", T = "rabbit"
输出: 3
解释:

如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

示例 2:

输入: S = "babgbag", T = "bag"
输出: 5
解释:

如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。 
(上箭头符号 ^ 表示选取的字母)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

https://leetcode-cn.com/problems/distinct-subsequences/

解法1

解法1使用动态规划方法。对于输入串S和T,我们构建一个dp[|S|+1][|T|+1]的矩阵。dp[i][j]表示目前我们看到了S的前i个字符S[0..i]与T的前j个字符T[0..j]时,我们能从S[0..i]中找到多少个与T[0..j]相等的子序列。当i或j等于0时,表示S或j为空串。

我们以示例2为例,给出矩阵dp的值。矩阵dp的第一列都为1,这是因为无论当前遇到的S有多长,我们都只能从S中找到一个与T相等的子序列,这个子序列就是空串。

矩阵应该以列主序的方式被填充,物理意义表示我们不断看的S新增的字符能找到更多的与T相等的解。如果S[i] ≠ T[j],则dp[i][j] = dp[i-1][j]。这很容易理解,因为从dp[i-1][j]到dp[i][j],S新增加了一个字符S[i]。新增的字符与T[j]不等,但这并不会影响解的个数,因为我们是从S中选取子序列(言外之意我们可以不选取新增的字符,不影响解的个数)。因此,新增字符后解的个数与新增字符前相等,有dp[i][j] = dp[i-1][j]。

图1矩阵dp

当S[i] = T[j]时,dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。这种情况比较复杂,我们遇到了一个新字符S[i],该字符与目前看到的T的最后一个字符T[j]相等。首先等式的前半部分dp[i-1][j]表示我们要累积之前的解,这部分与S[i] ≠ T[j]的情况一致。而后半部分表示,我们新遇到的字符S[i]与T[j]相等,我们就有机会利用S和T各自去掉最后一个字符的结果。

这么说有些难懂,我们以图1为例,分析dp[6][2]的情况。S[6]=’a’, T[2]=’a’满足S[i] = T[j]的条件,我们基于dp[5][2]的值,加上dp[5][1]的值。图中二叉树左子树描述了我们从S=”babgb”过渡到S=”babgba”,S新增了一个字符a,我们要累积S=”babgb”时的值。二叉树的右子树表述了,目前我们遇到的S与T的最后一个字符相等,我们就可以利用他们各自去掉最后一个字符的解。S去掉最后一个字符后S=”babgb”, T去掉最后一个字符T=”b”,我们能从S中找到3个子序列{S[0..0],S[2..2],S[4..4]}(即{“b”,”b”,”b”})与T=”b”相等。那么我们再把刚刚从S和T去掉的字符’a’补上,{S[0..1], S[2..3], S[4..5]}(即{“ab”,”ab”,”ab”})与T=”ba”还是相等,这种情况的”ba”是来自于{S[0]S[6], S[2]S[6], S[4]S[6]}。而二叉树的左分支是来自于S[0]S[1]

如果还不理解,我们反过来想如果S[i]与T[j]不等,我们还能利用dp[i-1][j-1]的值吗?假设S[i]=’x’, T[j]=’y’,S[0..i-1]=”babgb”, T[0..i-1]=”b”。我们取得dp[i-1][j-1]还是为3,即从S中取得{S[0..0],S[2..2],S[4..4]}(即{“b”,”b”,”b”})与T=”b”相等,我们再把S和T被去掉的最后一个字符恢复上, S[0..i]=”babgbx”, T[0..j]=”by”。那么很明显,S的子序列{“bx”, “bx”, “bx”}与T=”by”不等。

以下代码实现了上述分析,时间复杂度为O(|S|*|T|),空间复杂度为O(|S|*|T|)。

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1]; // dp[0][j]与dp[i][0]表示空串

        for (int i = 0; i <= s.length(); i++)
            dp[i][0] = 1;

        for (int j = 1; j <= t.length(); j++) {
            for (int i = 1; i <= s.length(); i++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[s.length()][t.length()];
    }
}

解法1优化-列主序的压缩存储

观察上述过程,矩阵dp以列主序被更新时,dp[i][j]仅依赖d[i-1][j]与dp[i-1][j-1]的值。也就是说,我们只保存当前列与前一列就能够计算出矩阵dp。我们创建一个矩阵dp[|S|+1][2],交替使用dp[i][0]与dp[i][1]。需要记住的是,当dp[i][0]或dp[i][1]被使用后一定要清零。我们可以用列索引对2取余来交替的选择dp[i][0]与dp[i][1],当计算过程结束后最终结果存储在第0列还是第1列取决于串T的长度是奇数还是偶数,所以我们取dp[|S|][0]与dp[|S|][1]的最大值就是答案。本方法的空间复杂度为O(2*|S|)

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][2];

        for (int i = 0; i <= s.length(); i++)
            dp[i][0] = 1;

        for (int j = 1; j <= t.length(); j++) {
            for (int i = 1; i <= s.length(); i++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j % 2] = dp[i - 1][(j - 1) % 2] + dp[i - 1][j % 2];
                } else {
                    dp[i][j % 2] = dp[i - 1][j % 2];
                }
            }

            // 清理前一列被用过的结果
            for (int i = 0; i <= s.length(); i++) {
                dp[i][(j - 1) % 2] = 0;
            }
        }

        return Math.max(dp[s.length()][0], dp[s.length()][1]);
    }
}

解法1优化-行主序的压缩存储

如果我们采用行主序的计算方式,只需要花费O(|T|)的空间复杂度就能够实现算法。采用行主序的计算方式我们必须采用倒序的方式更新dp!这是为什么呢?

假设我们使用顺序的更新方法,当遍历到S的第i个字符、T的第j个字符发生了S[i]=T[j],dp[j]被更新dp[j]=dp[j-1]+dp[j],当我们遍历到T的第j+1个字符时发生了S[i]=T[j+1]的情况,我们就会计算dp[j+1] = dp[j+1] + dp[j+1-1]。 请注意刚刚被计算的dp[j]是应该当S遍历到i+1个字符时才被使用的,也就是未压缩矩阵dp[i][j]的左上角位置。然而我们使用顺序更新的方式,使得本该被S[0..i+1]时使用的dp[j]被S[0..i]时使用了!!!

图2 行主序方式更新dp

图2描述了我们使用行主序的方式更新dp。我们采用倒序的方式更细,当i=1,j=1时,我们用dp[i-1]+dp[i] -> dp[i]。也就是说dp[i]只会依赖于前面一个值,我们采用逆序更新当方式就能防止要用到的值被覆盖。以下是使用行主序更新并使用压缩存储的代码。

class Solution {
    public int numDistinct(String s, String t) {
        int[] dp = new int[t.length() + 1]; // dp[0]表示空串

        dp[0] = 1; // dp[0]永远是1,因为不管S多长,都只能找到一个空串,与T相等

        for (int i = 1; i <= t.length(); i++)
            dp[i] = 0;

        for (int i = 0; i < s.length(); i++)
            for (int j = t.length() - 1; j >= 0; j--) {
                if (t.charAt(j) == s.charAt(i))
                    dp[j + 1] += dp[j];
            }
        return dp[t.length()];
    }
}

解法2

我们定义一个函数int numDistinct(String s, String t, int i, int j),函数numDistinct表示有串s与串t,能从s[i..end]找到多少个子序列等于t[j..end]。

为了在s中寻找子序列,我们在函数numDistinct中遍历x∈[i, |s|), 如果s[x] == t[j],那么说明s中的一个字符和t的一个字符相等,那么我们递归的调用函数numDistinct(s, t, x+1, j+1);如果s[x] != t[j],我们选取x+1看看是否与t[j]相等. 当参数j=|t|,说明我们找到了一个s的子序列与t相等。

以下是代码,但该代码并不能AC,因为它存在很多重复的递归调用。

class Solution {
    public int numDistinct(String s, String t) {
        return numDistinct(s, t, 0, 0);
    }

    /*
     * 函数numDistinct表示给串s与串t,能从s[i..end]找到多少个子序列等于t[j..end]
     */
    public int numDistinct(String s, String t, int i, int j) {
        if (j == t.length()) {
            return 1;
        }

        int res = 0;
        for (int x = i; x < s.length(); x++) {
            if (s.charAt(x) == t.charAt(j)) {
                res += numDistinct(s, t, x + 1, j + 1);

            }
        }

        return res;
    }
}

解法2优化

我们以例子s=“babgbag”,t=“bag”, 在函数numDistinct被调用时,打印出了调用记录。我们会发现调用记录中有很多重复的函数调用,这在串特别长的时候会产生非常多的重复调用,导致重复计算。

 Call numDistinct(babgbag, bag, 0, 0)
Call numDistinct(babgbag, bag, 1, 1)
Call numDistinct(babgbag, bag, 2, 2)
Call numDistinct(babgbag, bag, 4, 3)
Call numDistinct(babgbag, bag, 7, 3)
Call numDistinct(babgbag, bag, 6, 2)
Call numDistinct(babgbag, bag, 7, 3)
Call numDistinct(babgbag, bag, 3, 1)
Call numDistinct(babgbag, bag, 6, 2)
Call numDistinct(babgbag, bag, 7, 3)
Call numDistinct(babgbag, bag, 5, 1)
Call numDistinct(babgbag, bag, 6, 2)
Call numDistinct(babgbag, bag, 7, 3)

为什么会产生这么多numDistinct(babgbag, bag, 6, 2)调用呢?因为我们在s中能找到三个子序列”ba”,当发现s的’a’字符与t的’a’字符相等,就会产生递归调用numDistinct(babgbag, bag, 6, 2)。然后会从s的a字符开始向后扫描,来寻找是否存在与t的最后一个字符’g’相等。

为了避免重复的递归调用,我们可以创建一个数组cache[|s|+1][|t|+1], 全部初始化为-1. 每次递归调用前我们检查cache[i+1][j+1]是否为-1,如果不为-1则直接从cache取结果;如果cache[i+1][j+1]为-1,则发生递归调用。在函数返回前,我们将结果写入cache以供之后的递归调用使用。

class Solution {
    public int numDistinct(String s, String t) {
        int[][] cache = new int[s.length() + 1][t.length() + 1];

        for (int i = 0; i < cache.length; i++)
            for (int j = 0; j < cache[0].length; j++)
                cache[i][j] = -1;

        return helper(s, t, cache, 0, 0);
    }

    /*
     * 函数helper表示给串s与串t,能找到多少s[i..end] == t[j..end]
     */
    public int helper(String s, String t, int[][] cache, int i, int j) {
        if (j == t.length()) {
            return 1;
        }

        int res = 0;
        for (int x = i; x < s.length(); x++) {
            if (s.charAt(x) == t.charAt(j)) {
                if (cache[x + 1][j + 1] != -1)
                    res += cache[x + 1][j + 1];
                else
                    res += helper(s, t, cache, x + 1, j + 1);

            }
        }

        cache[i][j] = res;
        return res;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *