# [leetcode] Interleaving String

### Interleaving 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.

//方案一，递归，超时。复杂度o(n+m)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
//base condition
if(s1.empty() && s2.empty() && s3.empty()){
return true;
}
else if(s1.empty() || s2.empty() || s3.empty()){
return false;
}
else{
bool state;
if(s3[0] == s1[0]){
state = isInterleave(s1.substr(1, -1), s2, s3.substr(1, -1));
if(state == true){
return true;
}
}
if(s3[0] == s2[0]){
state = isInterleave(s1, s2.substr(1, -1), s3.substr(1, -1));
if(state == true){
return true;
}
}
return false;
}
}
};

class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
stack<size_t> st1;
stack<size_t> st2;
stack<size_t> st3;
size_t i = 0;
size_t j = 0;
size_t k = 0;
while(i < s1.size() && j < s2.size() && k < s3.size()){
if(s3[k] == s1[i] && s3[k] == s2[j]){
//move s2 and s3 then push the state into stack
st1.push(i);
st2.push(j + 1);
st3.push(k + 1);
}
if(s3[k] == s1[i]){
k++;
i++;
}
else if(s3[k] == s2[j]){
k++;
j++;
}
else if(st1.empty() == false){
i = st1.top();
j = st2.top();
k = st3.top();
st1.pop();
st2.pop();
st3.pop();
}
else{
return false;
}
}
return true;
}
};

//dp[i][j]表示用s1的前i个字符和s2的前j个字符能否interleave组成s3的前j+i个字符。
//dp[i][j] = (dp[i-1][j] && s1[i - 1] == s3[i + j - 1]) ||(dp[i][j-1] && s2[j - 1] == s3[i + j - 1])
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.size() + s2.size() != s3.size()) return  false;
bool dp[s1.size() + 1][s2.size() + 1];
memset(dp, false, sizeof(bool) * (s1.size() + 1) * (s2.size() + 1));
dp[0][0] = true;
for(size_t i = 1; i < s1.size() + 1; i++){
if(s1[i - 1] == s3[i - 1]){
dp[i][0] = true;
}
else{
break;
}
}
for(size_t j = 1; j < s2.size() + 1; j++){
if(s2[j - 1] == s3[j - 1]){
dp[0][j] = true;
}
else{
break;
}
}
for(size_t i = 1; i < s1.size() + 1; i++){
for(size_t j = 1; j < s2.size() + 1; j++){
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
}
}
return dp[s1.size()][s2.size()];
}
};

This site uses Akismet to reduce spam. Learn how your comment data is processed.