lintcode-118-不同的子序列

118-不同的子序列

给出字符串S和字符串T，计算S的不同的子序列中T出现的个数。

子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串，并且对剩下的字符的相对位置没有影响。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。

样例

给出S = "rabbbit", T = "rabbit"

返回 3

挑战

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

标签

字符串处理动态规划

思路

使用动态规划，首先考虑辅助空间为 O(n^2) 的情况，使用二维数组 dp[i][j] 表示 S[0...i] 中 T[0...j] 出现的个数

动态转移方程为：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j] （S[i]==T[j]）

dp[i][j] = dp[i-1][j] （S[i]!=T[j]）

过程如下：

过程中发现，新的取值仅仅和其左上和上部元素有关，所以可以用一维数组 dp[i] 代替二维数组

code

class Solution {

public:

    /**

     * @param S, T: Two string.

     * @return: Count the number of distinct subsequences

     */

    int numDistinct(string &S, string &T) {

        // write your code here

        int sizeS = S.size(), sizeT = T.size(), i = 0, j = 0;

        if(sizeS <= 0 || sizeT <= 0) {

            return 1;

        }

        vector<int> dp(sizeT+1, 0);

        dp[0] = 1;

        for(i=1; i<=sizeS; i++) {

            for(j=sizeT; j>0; j--) {

                if(S[i-1] == T[j-1]) {

                    dp[j] += dp[j-1];

                }

            }

        }

        return dp[sizeT];

    }

};

巴特西

lintcode-118-不同的子序列

118-不同的子序列

样例

挑战

标签

思路

code

最新文章

热门文章