sundeepblue
2/3/2014 - 7:19 PM

dp, Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B. Ex: A="abcd" B="xyz" C="axybczd".

dp, Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B. Ex: A="abcd" B="xyz" C="axybczd". answer is yes.

``````bool canInterleave(char *a, char *b, char *c) {
if(*a == '\0' && *b == '\0' && *c == '\0') return true;
if(*a == *b) {
if(*a == *c) return canInterleave(a+1, b, c+1) || canInterleave(a, b+1, c+1);
else return false;
}
if(*a == *c) return canInterleave(a+1, b, c+1);
if(*b == *c) return canInterleave(a, b+1, c+1);
}

// DP
bool canInterleave(char *a, char *b, char *c) {
int alen = strlen(a), blen = strlen(b), clen = strlen(c);
if(alen + blen != clen) return false;
if(alen == 0 && blen == 0 && clen == 0) return true;

vector<vector<bool>> dp(alen+1, vector<bool>(blen+1, false));
dp[0][0] = true; //
for(int i=1; i<blen+1; i++) {
if(b[i-1] == c[i-1] && dp[0][i-1]) dp[0][i] = true;
}
for(int i=1; i<alen+1; i++) {
if(a[i-1] == c[i-1] && dp[i-1][0]) dp[i][0] = true;
}
for(int i=1; i<alen+1; i++)
for(int j=1; j<blen+1; j++)
dp[i][j] = a[i-1]==c[i+j-1] && dp[i-1][j] ||
b[j-1]==c[i+j-1] && dp[i][j-1];
return dp[alen][blen];
}``````