# C++ Straightforward DP Solution

• We can use a 2D vector of boolean values to represent whether a substring a s3 can be composed by substring of s1 and s2. The recurrence relation is:

dp[i][j] = ture if

• s1[i-1] == s3[i+j-1] and dp[i-1][j]. Which means we want to use character s1[i-1] to compose s3[i+j-1]
• or s2[j-1] == s3[i+j-1] and dp[i][j-1]. Which means we want to use character s2[j-1] to compose s3[i+j-1]
``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int size1 = s1.size();
int size2 = s2.size();
int size3 = s3.size();
if(size1 + size2 != size3) return false;

vector<vector<bool>> dp(size1 + 1, vector<bool>(size2 + 1, false));
dp[0][0] = true;

for(int i = 0; i <= size1; ++i){
for(int j = 0; j <= size2; ++j){
if(i > 0 && s1[i-1] == s3[i+j-1] && dp[i-1][j]){
dp[i][j] = true;
}else if(j > 0 && s2[j-1] == s3[i+j-1] && dp[i][j-1]){
dp[i][j] = true;
}
}
}

return dp[size1][size2];
}
};
``````

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