注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex97 Interleaving String  

2015-05-27 23:28:45|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

两个字符interleave,构成第三个字符。
第一种思路,递归,超时

class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if ((len1 + len2) != len3)
return false;
bool result =
recursive(s1,0, s2,0, s3,0);
return result;

}
bool recursive(string s1,int index1 ,string s2,int index2, string s3,int index3)
{
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 == index1&&len2 == index2&&index3 == len3)
{
//三个字符都到末尾了
return true;
}
else
{
bool result = false;
char a, b;
if (index1 < len1 && index2 < len2)
{
a = s1[index1];
b = s2[index2];
if (a != b)
{
if (s1[index1] == s3[index3])
{
result = recursive(s1, index1 + 1, s2, index2, s3, index3 + 1);
return result;
}
else if (s2[index2] == s3[index3])
{
result = recursive(s1, index1, s2, index2 + 1, s3, index3 + 1);
return result;
}
return false;
}
else
{
bool mark1, mark2;
mark1 = false;
mark2 = false;
if (s2[index2] == s3[index3])
{
mark1 = recursive(s1, index1 + 1, s2, index2, s3, index3 + 1);
mark2 = recursive(s1, index1, s2, index2 + 1, s3, index3 + 1);
return mark1 || mark2;
}
else
return false;
}
}
else if (index1 < len1)
{
if (s1[index1] == s3[index3])
{
result = recursive(s1, index1 + 1, s2, index2, s3, index3 + 1);
return result;
}
else
return false;

}
else if (index2 < len2)
{
if (s2[index2] == s3[index3])
{
result = recursive(s1, index1, s2, index2+1, s3, index3 + 1);
return result;
}
else
return false;
}
}
}
};

又是动态规划,类似于LCS
这里开一个数组dp[i][j],表示为第一个数组的前i个元素,第二个数组的前j个元素是否是interleave的。
如果s1[i]==s3[k-1]  说明,dp[i][i] = dp[i-1][j],就是和去掉s1[i]状态是一样的
同理s2[j]==s3[k-1]  说明,dp[i][i] = dp[i][j-1],就是和去掉s2[j]状态是一样的
k表示的是当前s3的下标。盗用下面作者的一张图
ex97 Interleaving String - HT - HT·生活
 我们根据"aadbbcbcac"这个字符串在各自上走一个可以看到,画出的状态是一致的。

class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if ((len1 + len2) != len3)
return false;
bool result = traverse(s1, s2, s3);
return result;

}
bool traverse(string s1, string s2, string s3)
{
//动态规划进行遍历 开一个数组,dp[i][j]表示
//第一个数组的前i个,第二个string的前j个是interleave的
//所以就有转移方程
// if(s1[i]==s3[k-1]) dp[i][j] = dp[i-1][j]
// if(s2[j]==s3[k-1]) dp[i][j] = dp[i][j-1] k是s3的当前下标
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if ((len1 + len2) != len3)
return false;
vector<bool>tmp(len2+1,false);
vector<vector<bool>> dp(len1+1,tmp); //s1放在列的位置,s2放在行的位置

//为了方便,下标统一从1开始计算
dp[0][0] = true;
int i, j;
for (i = 1; i <= len1; i++) //第一列
{
if (s1[i - 1] == s3[i - 1])
dp[i][0] = true;
else
break;
}
for (j = 1; j <= len2; j++)
{
if (s2[j - 1] == s3[j - 1])
dp[0][j] = true;
else
break;
}

int k = 0; //用于记录s3的下标
for (i = 1; i <=len1; i++)
{
for (j = 1; j <= len2; j++)
{
k = i + j;
if (s1[i - 1] == s3[k - 1])
dp[i][j] = dp[i - 1][j] || dp[i][j];
if (s2[j - 1] == s3[k - 1])
dp[i][j] = dp[i][j - 1] || dp[i][j];
}
}
return dp[len1][len2];

}
};

参考
http://blog.csdn.net/doc_sgl/article/details/11714793
http://www.cnblogs.com/easonliu/p/3630964.html
  评论这张
 
阅读(22)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017