118. 不同的子序列-白红宇的个人博客

118. 不同的子序列

发布日期：2021-06-28 19:27:15 浏览次数：2 分类：技术文章

本文共 1184 字，大约阅读时间需要 3 分钟。

118. 不同的子序列

给定字符串

和

, 计算

的所有子序列中有多少个

子序列字符串是原始字符串删除一些(或零个)字符之后得到的字符串, 并且要求剩下的字符的相对位置不能改变. (比如

"ACE"

是

ABCDE

的一个子序列, 而

"AEC"

不是)

样例

样例 1:

输入: S = "rabbbit", T = "rabbit"

输出: 3

解释: 你可以删除 S 中的任意一个 'b', 所以一共有 3 种方式得到 T.

样例 2:

输入: S = "abcd", T = ""

输出: 1

解释: 只有删除 S 中的所有字符这一种方式得到 T

挑战

挑战时间复杂度 O(

n^2

), 空间复杂度 O(n) 的算法.

如果你不知道如何优化空间, O(

n^2

) 的空间复杂度也是可以通过的.

public class Solution {

/**

* @param S: A string

* @param T: A string

* @return: Count the number of distinct subsequences

public int numDistinct(String S, String T) {

// write your code here

int lens = S.length();

int lent = T.length();

if(lent==0) return 1;

int[] dp= new int[lens+1]; // number of matching to jth char in T for each char(ending by it) in S

dp[0]=1;

char c= ' ';

int temp=0;

int total =0;

for(int i=1;i<=lent;i++) {

//System.out.println("*********** "+ i+ " ************");

c = T.charAt(i-1);

int sum = 0;

for(int k=0;k<i;k++) {

sum+= dp[k];

dp[k]=0;

}

total =0;

for(int j=i;j<=lens;j++){

if(c== S.charAt(j-1)){

//System.out.println("sum="+ sum);

temp= dp[j];

dp[j]= sum;

total+=dp[j];

sum+= temp;

}else{

sum+=dp[j];

dp[j]=0;

}

//System.out.println("dp["+j+"]="+ dp[j]);

}

return total;

}

转载地址：https://blog.csdn.net/xwdrhgr/article/details/115891643 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：119. 编辑距离

下一篇：117. 跳跃游戏 II

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！