当前位置:网站首页>392. 判断子序列
392. 判断子序列
2022-07-04 12:48:00 【anieoo】
原题链接:392. 判断子序列
solution:
动态规划:
状态表示:dp[i][j]:表示s的前i个字母是否是t的前j的字母的子序列
状态计算: 如果s[i] == t[j]则,dp[i][j] = dp[i - 1][j - 1],否则dp[i][j] = dp[i][j - 1]
class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size(),n = t.size();
if(m > n) return false; //m长度大于n一定不是子序列
vector<vector<bool>> dp(m + 1, vector<bool> (n + 1, false));
//dp[i][j]:表示s的前i个字母是否是t的前j的字母的子序列
for(int i = 0;i <= n;i++) dp[0][i] = true;
for(int i = 1;i <= m;i++) {
for(int j = 1;j <= n;j++) {
if(s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[m][n];
}
};
双指针,只有s[j] == t[i],指针j才向后移动。
class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size(),n = t.size();
if(!m) return true;
if(m > n) return false;
for(int i = 0,j = 0;i < n;i++) {
if(s[j] == t[i]) j++;
if(j == m) return true;
}
return false;
}
};
边栏推荐
- [AI system frontier dynamics, issue 40] Hinton: my deep learning career and research mind method; Google refutes rumors and gives up tensorflow; The apotheosis framework is officially open source
- C#基础深入学习二
- unity不识别rider的其中一种解决方法
- Read the BGP agreement in 6 minutes.
- XML入门三
- ASP.NET Core入门一
- Scripy framework learning
- 7 月数据库排行榜:MongoDB 和 Oracle 分数下降最多
- C語言宿舍管理查詢軟件
- "Pre training weekly" issue 52: shielding visual pre training and goal-oriented dialogue
猜你喜欢
Go 语言入门很简单:Go 实现凯撒密码
How to choose a technology stack for web applications in 2022
Introduction to reverse debugging PE structure resource table 07/07
Summary of recent days (non-technical article)
ViewBinding和DataBinding的理解和区别
Distributed base theory
Personalized online cloud database hybrid optimization system | SIGMOD 2022 selected papers interpretation
【R语言数据科学】:交叉验证再回首
When MDK uses precompiler in header file, ifdef is invalid
Dgraph: large scale dynamic graph dataset
随机推荐
remount of the / superblock failed: Permission denied
C语言个人通讯录管理系统
Web知识补充
SQL language
Introduction to reverse debugging PE structure resource table 07/07
DGraph: 大规模动态图数据集
结合案例:Flink框架中的最底层API(ProcessFunction)用法
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
ASP.NET Core入门一
Personalized online cloud database hybrid optimization system | SIGMOD 2022 selected papers interpretation
面试拆解:系统上线后Cpu使用率飙升如何排查?
Detailed explanation of Fisher information quantity detection countermeasure sample code
硬件基础知识-二极管基础
The only core indicator of high-quality software architecture
2022KDD预讲 | 11位一作学者带你提前解锁优秀论文
C basic supplement
Animation and transition effects
Interviewer: what is the difference between redis expiration deletion strategy and memory obsolescence strategy?
免费、好用、强大的轻量级笔记软件评测:Drafts、Apple 备忘录、Flomo、Keep、FlowUs、Agenda、SideNote、Workflowy
C语言课程设计题