我要招人

去企业版

首页 > 试题广场 >

不同的子序列

[编程题]不同的子序列

热度指数：19635 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？

字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
例如：

S="nowcccoder", T = "nowccoder"

返回3

示例1

输入

"nowcccoder","nowccoder"

输出

算法知识视频讲解

查看答案及解析

Java

悟Kong

//运行时间过长
import java.util.ArrayList;
public class Solution {
    int num=0;
    int flag=1;
    public int numDistinct(String S, String T) {
        if(S==null||T==null)
            return 0;
        int len1=S.length();
        int len2=T.length();
        if(len2>len1){
            return 0;
        }
        ArrayList<Character> list=new ArrayList<Character>();
        backtracking(S,T,len2,0,list);
        return num;
    }
    public void backtracking(String S,String T,int k,int start,ArrayList<Character> list){
        if(k<0){
            return;
        }
        else if(k==0){
            for(int i=0;i<T.length();i++){
                if(list.get(i)!=T.charAt(i)){
                    flag=0;
                    break;
                }
            }
            if(flag==1){
                num++;
            }
            flag=1;
            return;
        }
        else{
            for(int i=start;i<S.length();i++){
                list.add(S.charAt(i));
                backtracking(S,T,k-1,i+1,list);
                list.remove(list.size()-1);
            }
        }
    }
}

发表于 2020-03-20 11:14:31 回复(0)

Java

AriesLi

class Solution {
    /**
     *  DP: 假设dp[i][j]是S中前i个字符构成的子串和T中前j个字符构成
     *  的子串匹配得到的子序列数量，求dp[S.length()][T.length()]
     *  1. 初始条件dp[i][0],S的前i的任意子串与空串有一个匹配的序列,dp[i][0]=1
     *     初始条件dp[0][j](j>0),S的空串与任意非空串无匹配的子序列,dp[0][j]=0
     *  2. 转义条件，求dp[i][j]的值有两种情况：
     *      1）S[i-1]!=T[j-1], dp[i][j]=dp[i-1][j] S的i-1位置与T的j-1不匹配
     *          那么符合的匹配序列数量和S的前i-1个字符的子串一样
     *      2) S[i]==T[j-1], dp[i][j]=dp[i-1][j]+dp[i-1][j-1] S的i-1与T的j-1匹配
     *          那么符合匹配的序列数等于前i-1就符合与T前j匹配的,加上S前i-1子串和
     *          T的前j-1子串匹配的。
     */
    public int numDistinct(String s, String t) {
        int[][] num = new int[s.length()+1][t.length()+1];
        for(int i=0; i<=s.length(); i++){
            num[i][0] = 1;
        }
        for(int i=1; i<=s.length(); i++){
            for(int j=1; j<=t.length(); j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    num[i][j] = num[i-1][j] + num[i-1][j-1];
                } else {
                    num[i][j] = num[i-1][j];
                }
            }
        }
        return num[s.length()][t.length()];
    }
}

发表于 2020-01-11 15:45:34 回复(0)

Java

力喜

java实现，动态规划算法，运行时间：27ms占用内存：9808k。

设S到第i个字母能匹配的T到第j个字母的个数为num[i][j],像之前编辑距离的题一样，需要拓展行和列，表示空串，任何字符串匹配搭配空串的个数为1，空串匹配到任何字符串的个数为0。判断如果S的第i个字母!=T的第j个字母，那么num[i][j]=num[i][j-1],即与左边元素值相等；当S的第i个字母==T的第j个字母时，那么num[i][j]=num[i][j-1]+num[i-1][j-1],即与左边元素和左上元素值之和相等，如：S：“rabbb”

T:"rab",这时num[4][6]=num[4][5]+num[3][5]。其中，num[4][5]=2,那2个匹配为："rab",(1)"ra b",(2)num[3][5]=1,那1个匹配为“ra”(3),而num[4][6]是“rab”,(1)"ra b"(2)和“ra b”(3)。

代码如下：

public class Solution {
     public int numDistinct(String S, String T) {
int length=T.length()+1;
int width=S.length()+1;
int[][]num=new int[length][width];
for(int i=0;i<length;i++)
    num[i][0]=0;
for(int n=0;n<width;n++)
    num[0][n]=1;
for(int j=1;j<length;j++)
    for(int m=1;m<width;m++)
    {
        if(S.charAt(m-1)==T.charAt(j-1))
        {num[j][m]=num[j][m-1]+num[j-1][m-1]; }
        else num[j][m]=num[j][m-1];
    }

return num[length-1][width-1];
    }
}

编辑于 2019-08-18 21:52:46 回复(0)

Java

阿拉要洗澡

* 思路：dp题。

* 状态定义：dp[i][j]代表s[0~i-1]中T[0~j-1]不同子串的个数。

* 递推关系式：S[i-1]!= T[j-1]： DP[i][j] = DP[i-1][j] （不选择S中的s[i-1]字符）

* S[i-1]==T[j-1]： DP[i][j] = DP[i-1][j-1]（选择S中的s[i-1]字符） + DP[i-1][j]（不选择S中的s[i-1]字符）

* 初始状态：第0列：DP[i][0] = 1，第0行：DP[0][j] = 0

public class Solution {

public int numDistinct(String S, String T) {

if(S.length()==0 || T.length()==0){

return 0;

}

int dp[][]=new int[S.length()+1][T.length()+1];

for(int i=0;i<S.length()+1;i++){

dp[i][0]=1;

}

for(int i=1;i<S.length()+1;i++){

for(int j=1;j<T.length()+1;j++){

if(S.charAt(i-1)==T.charAt(j-1) ){

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

}else{

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

}

return dp[S.length()][T.length()];

}

发表于 2017-08-13 14:20:58 回复(0)

Java

Holiday_12138

public class Solution {
    public int numDistinct(String S, String T) {
        int[][] dp = new int[S.length()+1][T.length()+1];
        dp[0][0] = 1;
        for(int i=1; i<=S.length(); i++)
            dp[i][0] = 1;
        for(int i=1; i<=S.length(); i++)
            for(int j=1; j<=T.length(); j++) {
                if(i < j)
                    dp[i][j] = 0;
                else {
                    if(S.charAt(i-1) == T.charAt(j-1))
                        dp[i][j] += dp[i-1][j-1];
                	dp[i][j] += dp[i-1][j];
            	}
            }
        return dp[S.length()][T.length()];
    }
}

发表于 2017-06-25 20:27:12 回复(0)

Java

城市里的养猫者

public int numDistinct(String S, String T) { // array creation int[][] mem = new int[T.length()+1][S.length()+1]; // filling the first row: with 1s for(int j=0; j<=S.length(); j++) {
        mem[0][j] = 1;
    } // the first column is 0 by default in every other rows but the first, which we need. for(int i=0; i<T.length(); i++) { for(int j=0; j<S.length(); j++) { if(T.charAt(i) == S.charAt(j)) {
                mem[i+1][j+1] = mem[i][j] + mem[i+1][j];
            } else {
                mem[i+1][j+1] = mem[i+1][j];
            }
        }
    } return mem[T.length()][S.length()];
}