【称号】
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is
a subsequence of "ABCDE" while "AEC" is
not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
【题意】
给定字符串S和T，通过删除S中的若干个字符能够得到T，则T称为S的子序列。问有多少种删法能够得到T
【思路】
DP问题。
定义A[i][j] (i>j)表示S[1...i]转化到T[1...j]的方式数(操作类型仅仅有一种。那就是从S中删除若干字符)。
转换方程例如以下：
假设S[i]==T[j], A[i][j]=A[i-1][j-1]+A[i-1][j];
假设S[i]!=T[j], A[i][j]=A[i-1][j];
初始化矩阵
起始点A[0][0]=1;
第一行A[0][i]=0;
第一列A[i][j]=1;
【代码】
class Solution {
public:
int numDistinct(string S, string T) {
if(S.length()==0 || S.length()==0)return 0;
if(S.length()<T.length())return 0; //假设S==T,返回1， 觉得有1种转换方式
vector<vector<int> >matrix(S.length()+1, vector<int>(T.length()+1, 0));
//初始化matrix[0][0]
matrix[0][0]=1;
//初始化对角线
for(int j=1; j<=T.length(); j++)
matrix[0][j]=0;
//初始化第一列
for(int i=1; i<=S.length(); i++)
matrix[i][0]=1;
//考虑其它i>j的情况
for(int i=1; i<=S.length(); i++){
for(int j=1; j<=T.length(); j++){
if(S[i-1]==T[j-1])matrix[i][j]=matrix[i-1][j-1]+matrix[i-1][j];
else matrix[i][j]=matrix[i-1][j];
}
}
return matrix[S.length()][T.length()];
}
};
版权声明：本文博客原创文章。博客，未经同意，不得转载。