【Lintcode】029.Interleaving String
2024-09-04 17:31:01
题目:
Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.
Example
For s1 = "aabcc"
, s2 = "dbbca"
- When s3 =
"aadbbcbcac"
, returntrue
. - When s3 =
"aadbbbaccc"
, returnfalse
.
题解:
Solution 1 ()
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
if (n1 + n2 != n3) {
return false;
}
vector<vector<int>> dp(n1 + , vector<int>(n2 + , false));
dp[][] = true;
for (int i = ; i <= n1; ++i) {
dp[i][] = dp[i - ][] && (s1[i - ] == s3[i - ]);
}
for (int i = ; i <= n2; ++i) {
dp[][i] = dp[][i - ] && (s2[i - ] == s3[i - ]);
}
for (int i = ; i <= n1; ++i) {
for (int j = ; j <= n2; ++j) {
dp[i][j] = (dp[i - ][j] && s1[i - ] == s3[i - + j]) || (dp[i][j - ] && s2[j - ] == s3[j - + i]);
}
}
return dp[n1][n2];
}
};
Solution 2 ()
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.length() + s2.length() != s3.length())
return false;
bool dp[s2.length() + ];
for(int i = ; i <= s1.length(); i++){
for(int j = ; j <= s2.length(); j++){
if(i == && j == )
dp[j] = true;
else if(i == )
dp[j] = (dp[j - ] && s3[i + j - ] == s2[j - ]);
else if(j == )
dp[j] = (dp[j] && s3[i + j - ] == s1[i - ]);
else
dp[j] = (dp[j] && s3[i + j - ] == s1[i - ]) || (dp[j - ] && s3[i + j - ] == s2[j - ]);
}
}
return dp[s2.length()];
}
};
DFS
Solution 3 ()
BFS
Solution 4 ()
最新文章
- 数据存储_SQLite (2)
- spring mvc 请求转发和重定向(转)
- HDU 2014
- Java连接mysql数据库
- 【6_100】Same Tree
- 小白学习mysql之索引初步
- XML基础概念
- jQuery checkBox 全选的例子
- php中的require() 语句的使用方法
- Ubuntu nfs 配置
- java面试题集2
- adbetj657k
- 项目中 添加 swift代码 真机调试 错误
- 201521123008《Java程序设计》第10周学习总结
- .NET在VS2008中生成DLL并调用
- BZOJ_1705_[Usaco2007 Nov]Telephone Wire 架设电话线_DP
- BZOJ5341[Ctsc2018]暴力写挂——边分治+虚树+树形DP
- Java作业二(2017-9-18)
- Optaplanner规划引擎的工作原理及简单示例(2)
- C#实现向excel中插入行列,以及设置单元格合并居中效果
热门文章
- ui-router $transitions 用法
- JQuery的一些思想,自己的一些见解!!!!
- go的timer定时器实现
- 1213 - Deadlock found when trying to get lock; try restarting transaction
- HDU 1452 Happy 2004(唯一分解定理)
- 【BZOJ】1003 Cards
- java常用的基础容器
- 性能测试--Jmeter录制、回放
- Wix Burn:如何将32位和64位的安装包制作成一个安装包
- python仪表盘