首页 > 试题广场 >

不同的子序列

[编程题]不同的子序列
  • 热度指数:19677 时间限制: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"

输出

3
//array(i , j ) 表示T[0,j] 在S[0,i] 中的匹配个数
//如果不使用S[i] , 那么f(i , j) = f(i-1 , j)
//如果使用了S[i] , 那么一定有 S[i] == T[j] , f( i , j ) = f(i -1 , j -1 )
//所以当S[i]==T[j]时,有array( i , j ) = array( i -1 , j ) + array(i - 1 , j - 1);
//当S[i]!=T[j]时,有 array( i , j ) = array( i -1 , j );
//在使用中不难发现该dp二维数组可以降维,注意改变数组元素值时由后往前
class Solution {
public:
int numDistinct(string S, string T) {
    int len=T.size();
    vector<int> array(len+1);
    array[0]=1;
    for(int i=1;i<S.size()+1;i++){
        for(int j=min(i,len);j>0;j--){
            if(S[i-1]==T[j-1])
                array[j]=array[j]+array[j-1];
        }
    }
    return array[len];
    }
};
编辑于 2016-10-09 11:12:32 回复(8)
正确理解题意:In plain English, my understanding of the problem is now this: How many ways can you generate the string T by only removing (but not reordering) characters in S?
发表于 2017-08-05 16:32:48 回复(4)
FUCK!每句话都得用有道查一下什么意思
发表于 2016-09-01 19:15:37 回复(2)
这种dp题目,不看答案一个字都写不出来,看完答案觉得一点都不难。。。

发表于 2017-11-29 16:06:02 回复(4)

原理不多说,上面的大神已经说得很清楚了,下面晒出我的示意图和代码:
图片说明

public int numDistinct(String S, String T) {
        if (S == null || T == null || T.length() == 0 || S.length() < T.length()) {
            return 0;
        }
        int sLen = S.length();
        int tLen = T.length();
        int[][] array = new int[sLen + 1][tLen + 1];
        // 初始化第一行,字符串S为"",除了子字符串为""的情况,结果全部为0
        for (int i = 1; i < tLen + 1; i++) {
            array[0][i] = 0;
        }
        // 初始化第一列,子字符串为"",结果全部为1
        for (int i = 0; i < sLen + 1; i++) {
            array[i][0] = 1;
        }
        for (int i = 1; i < sLen + 1; i++) {
            // j>i时子序列的长度大于源数列,结果为0,无需遍历
            // 或者for (int j = 1; j <= Math.min(i, tLen); j++)
            for (int j = Math.min(i, tLen); j > 0; j--) {
                // 如果当前位置的字母不同
                if (S.charAt(i - 1) != T.charAt(j - 1)) {
                    array[i][j] = array[i - 1][j];
                } else {// 如果当前位置的字母相同
                    array[i][j] = array[i - 1][j] + array[i - 1][j - 1];
                }
            }

        }
        return array[sLen][tLen];
    }

    // 因为当前结果只取决于上一行结果的当前位置和后面一位,因此可以降维
    public int numDistinct2(String S, String T) {
        if (S == null || T == null || T.length() == 0 || S.length() < T.length()) {
            return 0;
        }
        int sLen = S.length();
        int tLen = T.length();
        int[] array = new int[tLen + 1];
        array[0] = 1;
        for (int i = 1; i < sLen + 1; i++) {
            for (int j = Math.min(i, tLen); j > 0; j--) {
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    array[j] = array[j] + array[j - 1];
                }
            }
        }
        return array[tLen];
    }
编辑于 2018-05-25 11:29:39 回复(4)
/*
 *	思路:dp题。
 *	状态定义:dp[i][j]代表s[0~i-1]中T[0~j-1]不同子串的个数。
 *	递推关系式:S[i-1]!= T[j-1]:	DP[i][j] = DP[i][j-1] (不选择S中的s[i-1]字符)
 *				S[i-1]==T[j-1]:	DP[i][j] = DP[i-1][j-1](选择S中的s[i-1]字符) + DP[i][j-1]
 *  初始状态:第0列:DP[i][0] = 0,第0行:DP[0][j] = 1
 */

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

发表于 2016-08-15 00:04:42 回复(6)
class Solution {
public:
    int numDistinct(string S, string T) {
        map<int,int> dp;
        for(int j=0;j<S.size();j++)
            for(int i=T.size()-1;i>=0;i--)
            if(T[i]==S[j]){
               if(i!=0) dp[i]+=dp[i-1];
               else dp[0]++;
            }
        return dp[T.size()-1];
    }
};

发表于 2017-04-15 10:53:31 回复(0)
/*******************************************
distinct-subsequences问题,这个问题的大意就是
字符串S中有多少个子串是与T字符串相等的,子串
的定义就是去除S中的0或多个字符后的字符串,
用动态规划dp[i][j]表示s[0-i]与T[0-j]字符的结果,
动态规划问题,主要有二点:最优子结构和重叠子问题
假如,我们已经确定了S和T的结果是X,则当S[n]和T[m]
相等时,则S[n-1]和T[m-1]= S[n]和T[m]的,S[n-1]和T[m-1]=S[n]和T[m]
的,如果不想等,S[n-1]和T[m]=S[n]和T[m]的,这样
的话,动态规划公式就出来了:S[i]=T[j]时 dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
否则: dp[i][j]=dp[i-1][j];
************************************/
class Solution {
public:
int numDistinct(string S, string T) {
        int n=S.size(),m=T.size();
        int dp[n+1][m+1],i=0,j=0;
        dp[0][0]=1;
        for(i=1;i<n+1;i++)
        {
            dp[i][0]=1;
        
        for(i=1;i<m+1;i++)
        {
            dp[0][i]=0;
        }
        for(i=1;i<n+1;i++)
        {
            for(j=1;j<m+1;j++)
            {
                if(S[i-1]==T[j-1])
                {
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                //    cout<<"dp: "<<dp[i][j]<<endl;
                }else{
                    dp[i][j]=dp[i-1][j];
                //    cout<<"dp: "<<dp[i][j]<<endl;
                }
            }
        }
        return dp[n][m];
}
};

发表于 2018-04-10 21:28:06 回复(0)
/*
 *  思路: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)
class Solution:
    def numDistinct(self , S , T ):
        # write code here
        m = len(S)
        n = len(T)
        if m < n:
            return(0)
        elif m * n == 0 or S == T:
            return(1)
        else:
            res = [[0 for i in range(m)] for j in range(n)]
            for j in range(m):
                if S[j] == T[0]:
                    for x in range(j,m):
                        res[0][x] += 1
            for i in range(1,n):
                for j in range(1,m):
                    if S[j] == T[i]:
                            res[i][j] = res[i-1][j-1]+res[i][j-1]
                    else:
                        res[i][j] = res[i][j-1]
            return(res[n-1][m-1])


编辑于 2020-06-03 14:51:35 回复(0)
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)
class Solution {
public:
    int numDistinct(string S, string T) {
        S=" "+S,T=" "+T;
        int n=S.length(),m=T.length(),i,j;
        vector<vector<int> > dp(n+1,vector<int>(m+1,0));
        for(i=0;i<=n;i++) dp[i][0]=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(S[i]==T[j])
                    dp[i][j]+=dp[i-1][j-1];
            }
        return dp[n][m];
    }
};

发表于 2018-05-27 14:59:01 回复(0)
发表于 2018-03-28 21:21:09 回复(0)
public class Solution {  
        public int numDistinct(String S, String T) {  
            if (S == null || T == null) return 0;  
            if (S.equals("") || T.equals("")) return 0;  
              
            //table[i][j]表示S[0~i]中有多少个T[0~j]的个数  
            int[][] table = new int[S.length()][T.length()];  
              
            //给table第一行赋值,意思是S[0]中有多少个T[0~j]  
            //显然,S[0]最多包含一个T[0],故table[0][1~n]都为0  
            if (S.charAt(0) == T.charAt(0)) {  
                table[0][0] = 1;  
            }  
              
            for (int i = 1; i < S.length(); i++) {  
                char s = S.charAt(i);  
                  
                //给table[i][0]赋值,意思是S[0~i]中有多少个T[0]  
                if (s == T.charAt(0)) {  
                    table[i][0] = table[i - 1][0] + 1;  
                } else {  
                    table[i][0] = table[i - 1][0];  
                }  
                  
                for (int j = 1; j < T.length(); j++) {  
                    char t = T.charAt(j);  
                    if (s == t) {  
                        //如果用S[i]匹配T[j],那么S[0~i-1]敏感词有table[i-1][j-1]个T[0~j-1]  
                        //如果不用S[i]匹配T[i],那么S[0~i]敏感词有table[i-1][j]个T[0~j]  
                        table[i][j] = table[i - 1][j - 1] + table[i - 1][j];  
                    } else {  
                        //S[i]!=T[j]时,S[0~i]敏感词有table[i-1][j]个T[0~j]  
                        table[i][j] = table[i - 1][j];  
                    }  
                }  
                  
            }  
              
            return table[S.length() - 1][T.length() - 1];  
        }  
    }

发表于 2017-07-27 17:28:50 回复(0)
public int numDistinct(String s, String t) {
		if(s==null||t==null)
			return 0;
		int[][] res=new int[t.length()+1][s.length()+1];
		for(int i=0;i<=s.length();i++){
			res[0][i]=1;
		}
		for(int i=0;i<t.length();i++){
			for(int j=0;j<s.length();j++){
				if(t.charAt(i)==s.charAt(j))
					res[i+1][j+1]=res[i][j]+res[i+1][j];
				else
					res[i+1][j+1]=res[i+1][j];
				
			}
		}
		
		return res[t.length()][s.length()];
	}

发表于 2017-07-13 11:17:55 回复(0)
// 关键在于弄清楚对退公式与状态矩阵
// dp[i][j] 表示 S中的前i个字符构成的字符串包含 T 中前j个字符构成的字符串的 子串的个数
// 当S【i-1】 == t【j-1】时, 则新的dp值可以是 不使用第i个字符,却能构成T中j子串的个数dp[i][j] 加上
// 不使用第i个字符能构成T中j-1子串的个数dp[i-1][j-1]
// 否则,只能是等于dp[i-1][j]
class Solution {
public:
    int numDistinct(string S, string T) {
        int slen = S.length();
        int tlen = T.length();
        
        vector<vector<int>> dp;
        vector<int> temp(tlen+1,0);
        temp[0] = 1;
        
        for( int i = 0; i <= slen; i++)
            dp.push_back( temp );
        
        for( int i = 1; i <= slen ; i++)
            for(int j = 1 ; j <= tlen ; j++)
            {
            	if( S[i-1] == T[j-1] )
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            	else
                    dp[i][j] = dp[i-1][j];
        	}
         return dp[slen][tlen];
    }
};

发表于 2016-07-22 23:06:33 回复(2)
class Solution {
public:
    int numDistinct(string S, string T) {
        int l = T.length();
        vector<int> result(l+1);
        result[0] = 1;
        for(int i=1;i<=S.length();i++)
        	for(int j=min(i,l);j>0;j--)
        	{
        		if(S[i-1] == T[j-1])
        			result[j] = result[j] + result[j-1];
			}
        return result[l];
    }
};

发表于 2017-08-23 01:04:03 回复(0)

我们需要一个二维数组dp(i)(j)来记录长度为i的字串在长度为j的母串中出现的次数,这里长度都是从头算起的,而且遍历时,保持子串长度相同,先递增母串长度,母串最长时再增加一点子串长度重头开始计算母串。

首先我们先要初始化矩阵,当子串长度为0时,所有次数都是1,当母串长度为0时,所有次数都是0.当母串子串都是0长度时,次数是1(因为都是空,相等)。接着,如果子串的最后一个字母和母串的最后一个字母不同,说明新加的母串字母没有产生新的可能性,可以沿用该子串在较短母串的出现次数,所以dp(i)(j) = dp(i)(j-1)。如果子串的最后一个字母和母串的最后一个字母相同,说明新加的母串字母带来了新的可能性,我们不仅算上dp(i)(j-1),也要算上新的可能性。那么如何计算新的可能性呢,其实就是在既没有最后这个母串字母也没有最后这个子串字母时,子串出现的次数,我们相当于为所有这些可能性都添加一个新的可能。所以,这时dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。下图是以rabbbit和rabbit为例的矩阵示意图。计算元素值时,当末尾字母一样,实际上是左方数字加左上方数字,当不一样时,就是左方的数字。

示意图



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

发表于 2018-04-03 15:47:09 回复(14)
即使是中文,题目表述亦尚不明确!
发表于 2017-10-07 14:17:51 回复(0)
class Solution {
public:
    int numDistinct(string S, string T) {
        // write code here
        int lens = S.length();
        int lent = T.length();
        vector<vector<int>> dp(lens+1,vector<int>(lent+1));
        //第一行设置为0 第一列设置为1
        dp[0][0] = 1;
        for(int i=1;i<=lens;++i)
        {
            dp[i][0]=1;
            for(int j=1;j<=lent;++j)
            {
                if(S[i-1]==T[j-1])
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else 
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[lens][lent];
    }
};

发表于 2022-01-05 20:19:51 回复(0)