# My C++ DP solution

• This is a typical DP problem. Use an array to save the intermediate matching result. dp[i][j] represents if s3[0::i+j-1] is an interleaved version of s1[0::i-1] and s2[0::j-1]. The recursive equation is 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]) ). This equation only needs dp[i][] and dp[i-1][], so two rows are enough.

class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size(), len2 = s2.size(), len3 = s3.size(), row, col;
if(len1+len2!=len3) return false;//if the length doesn't match
if(!len1 || !len2) return s3 == s1+s2; // if at least one (s1 or s2) is empty, compare if the other equals to s3
bool dp[2][len2+1];

for(col=1, dp[0][0] = true; col<=len2;++col)
dp[0][col] = dp[0][col-1] && (s2[col-1] == s3[col-1]); // generate the first row of dp

for(row=1; row<=len1;++row)
for(col=1, dp[row%2][0] = dp[(row-1)%2][0] && (s1[row-1]==s3[row-1]) ; col<=len2;++col)
dp[row%2][col] = (dp[row%2][col-1] && s2[col-1] == s3[row+col-1]) ||
(dp[(row-1)%2][col] && s1[row-1] == s3[row+col-1]); // recursive equation
return dp[len1%2][len2];
}
};

• Here is my C version of the same solution, it works nice! Thanks for sharing!

//AC - 0ms - DP solution;
bool isInterleave(char* s1, char* s2, char* s3)
{
int len1=strlen(s1), len2=strlen(s2);
if(!len1 || !len2) return !strcmp(s1, s3) || !strcmp(s2, s3);
if(strlen(s3) != len1+len2) return false;
bool* cur=(bool*)malloc(sizeof(bool)*(len2+1));
bool* pre=(bool*)malloc(sizeof(bool)*(len2+1));
memset(pre, 0, sizeof(bool)*(len2+1));
pre[0] = true; //initialize boundary condition;
for(int i = 1; i <= len2; i++)
if(s2[i-1] == s3[i-1])
pre[i] = true;
else
break;
for(int i = 1; i <= len1; i++) //i and j represent length of s1 and s2 respectively;
{
for(int j = 0; j <= len2; j++)
cur[j] = (j>0 && cur[j-1] && s2[j-1]==s3[i+j-1]) ||
(pre[j] && s1[i-1]==s3[i+j-1]);
bool *t = pre; pre = cur; cur = t;
}
return pre[len2];
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.