当前位置:网站首页>LeetCode: Distinct Subsequences [115]
LeetCode: Distinct Subsequences [115]
2022-07-05 20:47:00 【全栈程序员站长】
大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
【称号】
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()];
}
};
版权声明:本文博客原创文章。博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117649.html原文链接:https://javaforall.cn
边栏推荐
- Abnova丨血液总核酸纯化试剂盒预装相关说明书
- 中国的软件公司为什么做不出产品?00后抛弃互联网;B站开源的高性能API网关组件|码农周刊VIP会员专属邮件周报 Vol.097
- 3.3、项目评估
- 重上吹麻滩——段芝堂创始人翟立冬游记
- Abbkine trakine F-actin Staining Kit (green fluorescence) scheme
- Kubernetes resource object introduction and common commands (V) - (configmap & Secret)
- Duchefa丨D5124 MD5A 培养基中英文说明书
- Clear app data and get Icon
- 线程池的使用
- Return to blowing marshland -- travel notes of zhailidong, founder of duanzhitang
猜你喜欢
产品好不好,谁说了算?Sonar提出分析的性能指标,帮助您轻松判断产品性能及表现
Use of thread pool
Duchefa丨S0188盐酸大观霉素五水合物中英文说明书
Hongmeng OS' fourth learning
Specification of protein quantitative kit for abbkine BCA method
Abbkine trakine F-actin Staining Kit (green fluorescence) scheme
leetcode:1755. 最接近目标值的子序列和
Which is the best online collaboration product? Microsoft loop, notion, flowus
Abbkine丨TraKine F-actin染色试剂盒(绿色荧光)方案
MySQL InnoDB架构原理
随机推荐
Rainbow 5.7.1 supports docking with multiple public clouds and clusters for abnormal alarms
Nprogress plug-in progress bar
Ros2 topic [01]: installing ros2 on win10
IC popular science article: those things about Eco
Abnova丨 CD81单克隆抗体相关参数和应用
[record of question brushing] 1 Sum of two numbers
AI automatically generates annotation documents from code
Duchefa d5124 md5a medium Chinese and English instructions
Go file path operation
3.3、项目评估
小程序事件绑定
重上吹麻滩——段芝堂创始人翟立冬游记
小程序代码的构成
Leetcode (347) - top k high frequency elements
Classic implementation of the basic method of intelligent home of Internet of things
解析创客教育的知识迁移和分享精神
leetcode:1139. 最大的以 1 为边界的正方形
Point cloud file Dat file read save
线程池的使用
Duchefa丨D5124 MD5A 培养基中英文说明书