Distinct Subsequences(不同子序列的个数)——b字符串在a字符串中出现的次数、动态规划
Given a string S and a string T, count the number of distinct subsequences ofT inS.
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相同。S的子串定义为在S中任意去掉0个或者多个字符形成的串。
递归求解:
首先找到在S中与T的第一个字符相同的字符,从这个字符开始,递归地求S和T剩下的串。T为空串时,返回1。因为空串本身是另外一个串的一个子序列。这个算法实现简单,但是果然不出意料,大集合超时。
Java代码:
public int numDistinct(String S, String T) {
// Start typing your Java solution below
// DO NOT write main() function
if (S.length() == 0) {
return T.length() == 0 ? 1 : 0;
}
if (T.length() == 0) {
return 1;
}
int cnt = 0;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == T.charAt(0)) {
cnt += numDistinct(S.substring(i + 1), T.substring(1));
}
}
return cnt;
}
遇到这种两个串的问题,很容易想到DP。但是这道题的递推关系不明显。可以先尝试做一个二维的表int[][] dp,用来记录匹配子序列的个数(以S ="rabbbit"
,T = "rabbit"
为例):
r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
从这个表可以看出,无论T的字符与S的字符是否匹配,dp[i][j] = dp[i][j - 1].就是说,假设S已经匹配了j - 1个字符,得到匹配个数为dp[i][j - 1](即若S[j]!=T[i],则该出现次数等于T[0-i]在S[0-(j-1)]出现的次数).现在无论S[j]是不是和T[i]匹配,匹配的个数至少是dp[i][j - 1]。除此之外,当S[j]和T[i]相等时,我们可以让S[j]和T[i]匹配,然后让S[j - 1]和T[i - 1]去匹配(T[0-(i-1)]在S[0-(j-1)]出现的次数*(T[i]==S[j])=1)
所以递推关系为:
dp[0][0] = 1; // T和S都是空串.
dp[0][1 ... S.length() - 1] = 1; // T是空串,S只有一种子序列匹配。
dp[1 ... T.length() - 1][0] = 0; // S是空串,T不是空串,S没有子序列匹配。
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0).1 <= i <= T.length(), 1 <= j <= S.length()
class Solution {
public:
int numDistinct(string S, string T) {
if(S.empty()||T.empty()) return ;
if(S.length()<T.length()) return ;
int dp[T.length()+][S.length()+];
dp[][]=;
for(int i=;i<=T.length();i++){
dp[i][]=;
}
for(int j=;j<=S.length();j++){
dp[][j]=;
}
for(int i=;i<=T.length();i++){
for(int j=;j<=S.length();j++){
dp[i][j]=dp[i][j-];
if(T[i-]==S[j-])
dp[i][j]+=dp[i-][j-];
}
}
return dp[T.length()][S.length()];
}
};
最新文章
- Linux 系统命令笔记
- split拆分数组长度问题
- 使用merge同时执行insert和update操作
- MyBaits一对一的查询方法
- GlassFish: 001 安装、启动
- IE下Debug BHO
- [javaSE] java获取文件列表
- TYVJ P2002 扑克牌
- Nginx基础知识之——配置文件信息(检查配置文件是否正确)
- iOS 微信 音频 视频自动播放
- PKUSC 模拟赛 day2 上午总结
- perl 分析mysql binlog
- HTML5新属性
- 什么是j2ee ??EJB与j2ee的关系?? 请看百度百科
- Yii2高级模板vendor和application非同级目录部署
- DropDownList如何绑定DataTable,如何绑定DataSet
- webservice07#契约优先#webservice实现简单的动态web项目
- Maven 学习总结 (六) 之 版本
- mysql 没有全外连接
- python自动化测试之异常及日志
热门文章
- python学习-- django 2.1.7 ajax 请求
- PHP smarty模版引擎基本安装
- 精通CSS高级Web标准解决方案(2-2 可视化格式模型之定位概述)
- Leetcode 451.根据字符出现频率排序
- webpack打包字体图标报错的解决办法
- 10个JavaScript难点--摘抄
- 【Dll】Run-Time Check Failure #0 - The value of ESP was not properly saved across a function call
- Linux之进程的等待与其内核实现解析
- /sys/class/gpio 文件接口操作IO端口(s3c2440)
- CMake安装或CMake Error at CMakeLists