0097. Interleaving String

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

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2+ t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

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

Example 2:

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

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lower-case English letters.

Analysis

dp[i][j]: from s1[0:i] and s2[0:j] can be combined to s3[0:i+j-1]

1. if current s[i+j-1] == s1[i] or s[i+j-1] == s2[j]: then meaning s[i+j-1] is possible to be formed by one of the two strings

2. else set to false

3. Time: $O(m \times n)$ where m is the size of s1, and n is the size of s2

4. Space: $O(m \times n)$ since need to populate the entire DP matrix

Code

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), k = s3.size();
        if (m + n != k)
            return false;
        bool dp[m+1][n+1];
        memset(dp, false, sizeof dp);
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++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[m][n];
    }
};

---

Last update: April 1, 2022