首页 > 代码库 > [leetcode-115-Distinct Subsequences]
[leetcode-115-Distinct Subsequences]
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
.
思路:
参考http://blog.csdn.net/fly_yr/article/details/50408457
题目给定两个字符串,选择只可以用删除字符的方法从第一个字符串变换到第二个字符串,求出一共有多少种变换方法;
又是动态规划思想应用的典型题目。
- 定义二维数组dp[i][j]为字符串s(0,i)变换到t(0,j)的变换方法。
- 如果S[i]==T[j],那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。意思是:如果当前S[i]==T[j],那么当前这个字母即可以保留也可以抛弃,所以变换方法等于保留这个字母的变换方法加上不用这个字母的变换方法。
- 如果S[i]!=T[j],那么dp[i][j] = dp[i-1][j],意思是如果当前字符不等,那么就只能抛弃当前这个字符。
- 递归公式中用到的dp[i][0] = 0(把任意一个字符串变换为一个空串只有一个方法)
class Solution { public: /*用删除的方法将串s变换到t,计算变换方法数*/ int numDistinct(string s, string t) { if (s.empty() || t.empty()) return 0; else if (s.length() < t.length()) return 0; else { //动态规划 int ls = s.length(), lt = t.length(); /*保存由字符串s(0,i) --> t(0,j)的方法数*/ vector<vector<int> > dp(ls + 1, vector<int>(lt + 1, 0)); dp[0][0] = 1; for (int i = 0; i < ls; ++i) { /*s(0,i) 转换为 t(0)的方法数为1*/ dp[i][0] = 1; }//for for (int i = 1; i <= ls; ++i) { for (int j = 1; j <= lt; ++j) { /*首先不管当前字符是否相同,为dp[i][j]赋初值*/ dp[i][j] = dp[i - 1][j]; if (s[i-1] == t[j-1]) { /*如果s和t的当前字符相同,有两种选择保留或不保留*/ dp[i][j] += dp[i - 1][j - 1]; }//if }//for }//for return dp[ls][lt]; } } };
[leetcode-115-Distinct Subsequences]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。