LintCode 不同的子序列

时间:2021-6-3 作者:qvyue

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

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

返回 3

分析:这里我们可以用f(i,j)表示S中前i个字符串中,T的前j个字符出现的次数,不管S[i]和T[j]相不相等,首先f(i,j)=f(i-1,j),其次要是S[i]==T[j]的话,f(i,j) = f(i-1,j)+f(i-1,j-1),可以看到,i的状态只与i-1有关,于是可以用滚动数组来进行优化。代码类似01背包。

public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
   public int numDistinct(String S, String T) {
        if(null == S || null == T)
            return 0;
        // commons 表示S中的前i个字符包含T的前j个字符的个数
        int[][] commons = new int[S.length() + 1][T.length() + 1];
        for(int i = 0;i 
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。