# C++ bottom-up solution using dynamic programming (3ms)

• ``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {

// Edge cases
if( s3.length() != s1.length() + s2.length() )
return false; // no way to interleave
if( s3 == s1 + s2 || s3 == s2 + s1 )
return true; // trivial concatenation

// Create space for memo, and initialize all entries to false
bool** memo = new bool*[ s1.length() + 1 ];
for( int i = 0; i <= s1.length(); ++i ) {
memo[i] = new bool[ s2.length() + 1 ];
for( int j = 0; j <= s2.length(); ++j )
memo[i][j] = false;
}

// memo[i][j] = can we interleave s1[i:] and s2[j:] to get s3[i + j:]?

// Base cases:
// 1. memo[length of s1][length of s2] = true, because we can get "" by interleaving "" and ""
// 2. We also have memo[length of s1][i] = (s3[length of s1 + i:] == s2[i:]) and similar s1 <--> s2

memo[ s1.length() ][ s2.length() ] = true; // empty strings interleaved produces empty string
int k = 0;
while( s3[ s3.length() - 1 - k] == s2[ s2.length() - 1 - k]  && k < s2.length() ) {
memo[ s1.length() ][ s2.length() - 1 - k ] = true;
++k;
}
k = 0;
while( s3[ s3.length() - 1 - k] == s1[ s1.length() - 1 - k] && k < s1.length() ) {
memo[ s1.length() - 1 - k ][ s2.length() ] = true;
++k;
}

// The recurrence rule is that we can interleave s1[i:] and s2[j:] to get s3[i + j: ] iff either
//      s1[i] == s3[i + j] and we can interleave s1[i + 1:] and s2[j:] to get s3[i + j + 1:], or
//      s2[j] == s3[i + j] and we can interleave s1[i:] and s2[j + 1:] to get s3[i + j + 1:].
// We just apply this recurrence.
for( int i = s1.size() - 1; i >=0; --i )
for( int j = s2.size() - 1; j >= 0; --j ) {
memo[i][j] = ( s3[i + j] == s2[j] && memo[i][j + 1] ) || ( s3[i + j] == s1[i] && memo[i + 1][j] );
}

bool result = memo[0][0];

// Deallocate memory
for( int i = 0; i <= s1.size(); ++i )
delete[] memo[i];
delete[] memo;

return result;
}
};
``````

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