alg-最长公共子序列
2024-10-09 00:31:16
class Solution {
public:
std::string LongestCommonSubsequence(const std::string& s1, const std::string& s2) {
if (s1.empty()||s2.empty()) {
return 0;
}
//dp
std::vector<std::vector<int>> dp(s1.size()+1,std::vector<int>(s2.size()+1,0));
for(int i=1;i<s1.size()+1;i++) {
for(int j=1;j<s2.size()+1;j++) {
dp[i][j]=(s1[i-1]==s2[j-1])?dp[i-1][j-1]+1:std::max(dp[i-1][j],dp[i][j-1]);
}
}
//search path
std::string res;
for(int i=s1.size(),j=s2.size();i>0&&j>0;) {
if(s1[i-1]==s2[j-1]) {
res.insert(0,1,s1[i-1]);
i--;
j--;
}
else {
if(dp[i-1][j]>dp[i][j-1]) {
i--;
}
else {
j--;
}
}
}
return res;
}
};
最新文章
- 学习笔记 MYSQL报错注入(count()、rand()、group by)
- [LeetCode] Burst Balloons 打气球游戏
- 我的VPN推荐经历
- 为什么那么多人想开发一元夺宝类app？
- Ubuntu中启用关闭Network-manager网络设置问题！
- 安卓第十天笔记-fragment
- VS的工程链接优化的问题
- ORACLE之手动注册监听listener。alter system set local_listener="XXX"
- 【Xamarin挖墙脚系列：Xamarin开发环境配置需求】
- logstash 使用grok正则解析日志
- 如何使用dynamic
- python entry points 例子
- Vs2012 构建配置 Lua5.2.3
- BackgroundWorker组件使用总结
- SpringMVC同时使用<mvc:resources … />和日期转换Formatter时出现问题的解决方法
- MIPI DSI之DBI DPI含义和区别（3-1）
- 简单的了解一下AQS吧
- jqgrid点击搜索无法重置参数问题
- 数据库中关于convert的参数学习（转化函数用法）
- PythonStudy——字符串扩展方法 String extension method