97. Interleaving String

• Difficulty: Hard

• Topics: String, Dynamic Programming

• Similar Questions:

Problem:

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

Solutions:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.length() != s1.length() + s2.length())   return false;

        int len1 = s1.length();
        int len2 = s2.length();

        vector<vector<bool>> dp (len1 + 1, vector<bool>(len2 + 1, false));

        dp[0][0] = true;
        for (int i = 1; i <= len1; ++i) {
            dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1]); 
        }

        for (int j = 1; j <=len2; ++j) {
            dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1]);
        }

        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                // i, j denotes count
                dp[i][j] = (s3[i+j -1] == s1[i-1] ? dp[i-1][j] : false ) || (s3[i+j - 1] == s2[j-1] ? dp[i][j-1] : false);            
            }
        }

        /*
        for (int i = 0; i <= len1; ++i) {
            for (int j = 0; j <=len2; ++j) {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        */

        return dp[len1][len2];
    }
};