97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

dp[i][j]代表s3[0...i + j - 1]是否可以由s1[0...i - 1]和s2[0...j - 1]交織組合成。

// Dynamic Programming
bool isInterleave(string s1, string s2, string s3) { // time: O(n1 * n2); space: O(n1 * n2)
    int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
    if (n3 != n1 + n2) return false;
    vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false));
    for (int i = 0; i <= n1; ++i) {
        for (int j = 0; j <= n2; ++j) {
            if (i == 0 && j == 0) {
                dp[i][j] = true;
            } else if (i == 0) {
                dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];
            } else {
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || 
                            (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        }
    }
    return dp.back().back();
}