本文主要是介绍leetcode115，字符串T中序列S的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
（转）原文：https://blog.csdn.net/XX_123_1_RJ/article/details/80789223
问题描述：
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
示例1：
输入: S = "rabbbit", T = "rabbit"
输出: 3解释:如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。(上箭头符号 ^ 表示选取的字母)rabbbit
^^^^ ^^rabbbit
^^ ^^^^rabbbit
^^^ ^^^示例2：
输入: S = "babgbag", T = "bag"
输出: 5
解释:如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。 (上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag^ ^^
babgbag^^^
问题分析：
标准动态规划题目，以S = "babgbag", T = "bag"，为例，dp[i][j]表示字符串S的前j个元素中有多少个 T的前i个元素，可以得到下图：
计算dp[i][j]时要判断S[j-1]==T[i-1],切勿搞错
当i=2，j=6时，表示字符串 'babgbag' 中有多少个 'bag'，此时，要想知道现在有多少个'bag', 那么只需知道 j=5 时有多少个 'ba' 和已经有了多少个'bag', 接着再判断 S[j] ==T[i] 是否成立，如果成立，dp[i][j] = 'ba'的个数 + 已有'bag'的个数，dp[i][j] = 已有'bag'的个数。
所以dp方程式为：dp[i][j] = dp[i][j-1] + dp[i-1][i-j] * (T[i-1] == S[j-1])（dp[i][j-1]对应绿色方格，dp[i-1][i-j]对应黄色方格）。
代码如下：
class Solution {
public:int numDistinct(string S, string T) {int dp[T.size() + 1][S.size() + 1];for (int i = 0; i <= S.size(); ++i) dp[0][i] = 1; for (int i = 1; i <= T.size(); ++i) dp[i][0] = 0; for (int i = 1; i <= T.size(); ++i) {for (int j = 1; j <= S.size(); ++j) {dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0);}}return dp[T.size()][S.size()];}
};此题另解：
递归求出s的所有子序列，求和S相同的子序列个数即可(此法leetcode超时）
void Subsequence(string str1,int i,string t,string out,int &num){if(i==str1.size()){if(strcmp(out.c_str(),t.c_str())==0)num++;return ;}Subsequence(str1,i+1,t,out+str1[i],num);Subsequence(str1,i+1,t,out,num);}int numDistinct(string s, string t) {int num=0; Subsequence(s,0,t,"",num);return num;}
这篇关于leetcode115，字符串T中序列S的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
