[LeetCode] Interleave String
Given s1, s2, s3, 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.
isInterleaving(s1,len1,s2,len2,s3,len3)
= (s3.1stChar == s1.1stChar) && isInterleaving(s1,len1 - 1,s2,len2,s3,len3 - 1)
||(s3.1stChar == s2.1stChar) && isInterleaving(s1,len1,s2,len2 - 1,s3,len3 - 1)
1. 一个递归的思路: 在每一个match前决策并递归到余下的substring. O(2^n) --> 小数据量可以通过，但大数据量时会超时
[cpp]
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s1=="" && s2=="" && s3=="")
{
return true;
}
else if(s3=="")
{
return false;
}
bool result1=false,result2=false;
string ns1,ns2,ns3;
if( s1.length() > 1)
ns1=s1.substr(1,s1.length()-1);
else
ns1="";
if( s2.length() > 1)
ns2=s2.substr(1,s2.length()-1);
else
ns2="";
if( s3.length() > 1)
ns3=s3.substr(1,s3.length()-1);
else
ns3="";
if(s1.length()>0 && s3[0] == s1[0])
{
result1=isInterleave(ns1,s2,ns3);
}
if(s2.length()>0 && s3[0]==s2[0])
{
result2=isInterleave(s1,ns2,ns3);
}
return result1+result2;
}
};
2. Dynamic Programming: 20ms pass all "judge large" cases
思路：M[i][j]==1: 长度为i+j的s3，可以由s1的前i个字符和s2的前j个字符交织成
初始化: M[0][:]=1 if s3可全部由s3=prefix(s1)
M[:][0]=1 if s3=prefix(s2)
再根据公式updateM[i][j]
因为s3.length()>=1, 所以M[0][0]没有定义，M[s1.length][s2.length]必须定义，故矩阵的大小为(s1.length+1)*(s2.length+1)
[cpp]
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s1.length()+s2.length() != s3.length())
{
return false;
}
if(s1=="" && s2=="" & s3=="")
return true;
if(s1=="" && s2!=s3) return false;
if(s1=="" && s2==s3) return true;
if(s2=="" && s1!=s3) return false;
if(s2=="" && s1==s3) return true;
vector<vector<int>> m((s2.length()+1),vector<int>(s1.length()+1));
for(int i=0;i<s1.length();i++)
{
if(s1[i]==s3[i])
{ m[0][i+1]=1;}
else
break;
}
for(int i=0;i<s2.length();i++)
{
if(s2[i]==s3[i])
{ m[i+1][0]=1;}
else
break;
}
for(int i=1;i<s1.length()+1;i++)
{
for(int j=1;j<s2.length()+1;j++)
{
if(m[j][i-1]==1 && s3[i+j-1]==s1[i-1])
{
m[j][i]=1;
}
else if(m[j-1][i]==1 && s3[i+j-1]==s2[j-1])
{
m[j][i]=1;
}
else
{
&
补充：综合编程 , 其他综合 ,上一个：算法导论第一章
下一个：Creo二次开发--函数--与颜色有关的函数
