LintCode-交叉字符串
2024-09-05 17:03:39
给出三个字符串:s1、s2、s3,推断s3是否由s1和s2交叉构成。
您在真实的面试中是否遇到过这个题?
Yes
例子
比方 s1 = "aabcc" s2 = "dbbca"
- 当 s3 = "aadbbcbcac",返回 true.
- 当 s3 = "aadbbbaccc", 返回 false.
挑战
要求时间复杂度为O(n^2)或者更好
分析:两个字符串的问题,大部分都能够用dp[i][j]表示第一个字符串前i个字符第二个字符串前j个字符的匹配情况来解决
代码:
class Solution {
public:
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true of false.
*/
bool isInterleave(string s1, string s2, string s3) {
// write your code here
if(s3.length()!=s1.length()+s2.length())
return false;
if(s1.length()==0)
return s2==s3;
if(s2.length()==0)
return s1==s3;
vector<vector<bool> > dp(s1.length()+1,vector<bool>(s2.length()+1,false));
dp[0][0] = true;
for(int i=1;i<=s1.length();i++)
dp[i][0] = dp[i-1][0]&&(s3[i-1]==s1[i-1]);
for(int i=1;i<=s2.length();i++)
dp[0][i] = dp[0][i-1]&&(s3[i-1]==s2[i-1]);
for(int i=1;i<=s1.length();i++)
{
for(int j=1;j<=s2.length();j++)
{
int t = i+j;
if(s1[i-1]==s3[t-1])
dp[i][j] = dp[i][j]||dp[i-1][j];
if(s2[j-1]==s3[t-1])
dp[i][j] = dp[i][j]||dp[i][j-1];
}
}
return dp[s1.length()][s2.length()];
}
};
最新文章
- [LeetCode] Palindrome Linked List 回文链表
- Consul Windows 安装
- 基于bootstrap的后台二级垂直菜单[转]
- exception &#39;yii\base\ErrorException&#39; with message &#39;Class &#39;MongoClient&#39; not found&#39;
- nodejs前端跨域访问
- table中的标题行冻结的简单实现
- KMP算法 - 求最小覆盖子串
- easyui中对于dialog页面传值的接收
- hbase的rowkey简单设计
- DHT11温湿度传感器
- ibatis.net 多线程的调试
- apache开源项目-- NiFi
- C#面向对象——方法的重载及构造函数、静态对象。
- Team Foundation Server操作说明
- php 中const和 define的区别
- css的repaint和reflow
- hadoop2.x源码编译
- oracle 汉字转化拼音函数
- Stopwatch + C#打印日志方法
- Asp.Net初学小结