https://leetcode.com/problems/interleaving-string/
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
vector<vector<int>> f(l1 + 1, vector<int>(l2 + 1, 0));
if (l3 != l1 + l2) {
return false;
}
f[0][0] = l1 == 0 && l2 == 0 && l3 != 0 ? false : true;
for (int i = 1; i <= l1; i++) {
f[i][0] = f[i-1][0] && s1[i-1] == s3[i-1];
}
for (int j = 1; j <= l2; j++) {
f[0][j] = f[0][j-1] && s2[j-1] == s3[j-1];
}
for (int i = 1; i <= l1; i++) {
for (int j = 1; j <= l2; j++) {
if (f[i-1][j] && s1[i-1] == s3[i+j-1]) {
f[i][j] = f[i-1][j];
}
if (f[i][j-1] && s2[j-1] == s3[i+j-1]) {
f[i][j] = f[i][j-1];
}
}
}
return f[l1][l2];
}
};
