[LeetCode] Distinct Subsequences

题目描述

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

大意是求S的子串有多少个和T一样

解法来自Stack Overflow

我只是大概翻译一下,我也用了这个解法,觉得他讲得很好不需要我再加内容再解释,
它只是有一个错误,二维矩阵里j可以正序也可以倒序,而且初始化好像是需要的,后面再说,先看解法

首先,我们假设 S 的长度为 m, T 的长度为 n,我们让 S{i} 表示起点从i开始的S的子串。举个栗子:如果 S = “abcde”,
S{0} = “abcde”
S{4} = “e”
S{5} = “”
我们将同样的规则应用于T

我们把N[i][j]用于表示 S{i} 和 T{j} 的distinct subsequence count,我们需要的是N[0][0]。(因为他们是两个完整的字符串)

Let N[i][j] be the distinct subsequences for S{i} and T{j}. We are interested in N[0][0] (because those are both full strings).

有两种情况:对于所有i的N[i][n] ,和对于所有j < n的N[m][j]。
对于N[i][n],S中有多少个字串和T{n} = “”相同呢?当然只有一个 (N[i][n] = 1)
对于N[m][j],S{m} = “” 有多少字串和 T{j} 相同呢?明显没有啊 (N[m][j] = 0)

现在,给以任意的i和j,我们来试着找找看递推公式吧。它包含两种情况

  1. 如果 S[i] != T[j],那么我们就有 N[i][j] = N[i+1][j],因为不相等嘛,最大的情况肯定是和T不变但S比现在短的情况一样,所以就是和N[i+1][j]相等

  2. 如果 S[i] = T[j],这样的话我们其实可以选择匹配或者不匹配字符串,如果匹配,那么N[i+1][j+1]可以到达现在的状态,两个子串的start都向前移动了一位;如果不匹配,那么就是和上面的情况一样。我们有两种选择,所以现在的状态应该是N[i][j] = N[i+1][j] + N[i+1][j+1]

然后我们利用DP的方法去把整个N矩阵填满,先设置好边界:

N[m][j] = 0; // for 0 <= j < n
N[i][n] = 1; // for 0 <= i <= m
N[m][n] = 1; // focus!!!

由于递推公式的依赖关系,我们需要将剩下的矩阵用i向后移动,j方向无所谓啦,在二维递推矩阵里,j正着反着结果一样

for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
        if (S[i] == T[j]) {
            N[i][j] = N[i+1][j] + N[i+1][j+1];
        } else {
            N[i][j] = N[i+1][j];
        }
    }
}

我们可以用一个非常重要的技巧,讲这个空间优化到一维,因为是倒叙,而且每次i层是用i+1层所有已经填满的数据来进行计算的,那么就可以用一个一维数组f来表示。但这里要注意的是,f的j,必须是正序,为了避免重复计算。

前面我们说了:如果S[i] 和 T[j]相等,那么对应到一维,f[i][j]可能需要用到f[i+1][j+1]的值,如果你先倒序计算了后面的,那么f[i+1][j+1]就已经被i层的覆盖掉了,在一维数组里,i层和i+1层是一样一样的呀~

然后把这些用到算法里


// initialization
f[j] = 0; // for 0 <= j < n
f[n] = 1;

for (int i = m - 1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        if (S[i] == T[j]) {
            f[j] = f[j] + f[j+1];
        } else {
            f[j] = f[j];
        }
    }
}

还可以进一步优化

把这个

if (S[i] == T[j]) {
    f[j] += f[j + 1];
}

变成

f[j] += (S[i] == T[j]) * f[j+1];

然后就变成了

f[j] = 0; // for 0 <= j < n
f[n] = 1;

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        f[j] += (S[i] == T[j]) * f[j+1];
    }
}