Description

Submission

class Solution {
    int dp[101][101];
public:
    bool isInterleave(string s1, string s2, string s3) {
        
        if(s1.length() + s2.length() != s3.length()) return false;
        if(s1.empty()) return s2 == s3;
        if(s2.empty()) return s1 == s3;
        dp[0][0] = 1;
        for(int len = 1; len <= s3.size(); ++len) {
            for(int i = 0; i <= s1.length(); ++i) { // i: length of s1
               int j = len - i; // j: length of s2
               if(j > s2.length()) continue;
               if(i == 0) dp[0][j] = s3.substr(0, j) == s2.substr(0, j);
               else if(j == 0) dp[i][0] = s1.substr(0, i) == s3.substr(0, i);
               else dp[i][j] = (dp[i][j-1] && s2[j-1] == s3[len-1]) || (dp[i-1][j] && s1[i-1] == s3[len-1]);
               if(len == s3.size() && dp[i][j]) return true;
            }
        }
        for(int i = 0; i < 101; ++i) {
            for(int j = 0; j < 101; ++j) {
                cout << dp[i][j];
            }
            cout << endl;
        }
        return false;
        
    }
};


// dp[i][j]: whether s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j];
// dp[i][j] == dp[i-1][j] && s1[i] == s3[i+j]