# 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

# Solution

Approach 1: DP.

Approach 2: DP with less space.

Approach 3: Recursion + memorization.

# Code (Python)

Approach 1:

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        # match[i][j]: if the first i letters of s1 and first j letters of s2 interleaves the first i+j letters of s3
        match = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
        
        for i in range(len(match)):
            for j in range(len(match[0])):
                if i == 0 and j == 0:
                    match[i][j] = True
                    continue
                if i == 0:
                    match[i][j] = (s3[i+j-1] == s2[j-1] and match[i][j-1])
                    continue
                if j == 0:
                    match[i][j] = (s3[i+j-1] == s1[i-1] and match[i-1][j])
                    continue
                if i > 0 and s3[i+j-1] == s1[i-1]:
                    match[i][j] = match[i][j] or match[i-1][j]
                if j > 0 and s3[i+j-1] == s2[j-1]:
                    match[i][j] = match[i][j] or match[i][j-1]
        
        return match[-1][-1]
        # space can be optimized to linear

# Code (C++)

Approach 1:

// DP
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size();
        int n2 = s2.size();
        int n3 = s3.size();
        if (n1 + n2 != n3)
            return false;
        if (n1 == 0)
            return s2 == s3;
        if (n2 == 0)
            return s1 == s3;
        bool match[n1+1][n2+1];
        match[0][0] = true;
        for (int i = 0; i <= n1; ++i)
        {
            for (int j = 0; j <= n2; ++j)
            {
                if (i + j > 0)
                {
                    match[i][j] =
                        (i > 0 && s1[i-1] == s3[i+j-1] && match[i-1][j]) ||
                        (j > 0 && s2[j-1] == s3[i+j-1] && match[i][j-1]);
                }
            }
        }
        return match[n1][n2];
    }
};

Approach 2:

// DP with less space.
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size();
        int n2 = s2.size();
        int n3 = s3.size();
        if (n1 + n2 != n3)
            return false;
        if (n1 == 0)
            return s2 == s3;
        if (n2 == 0)
            return s1 == s3;
        bool match[n2+1];
        match[0] = true;
        for (int i = 0; i <= n1; ++i)
        {
            for (int j = 0; j <= n2; ++j)
            {
                if (i + j > 0)
                {
                    match[j] =
                        (i > 0 && s1[i-1] == s3[i+j-1] && match[j]) ||
                        (j > 0 && s2[j-1] == s3[i+j-1] && match[j-1]);
                }
            }
        }
        return match[n2];
    }
};

Approach 3:

// Recursion + memorization.
class Solution {
private:
    unordered_map<string,bool> umap;
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1 > s2)
            std::swap(s1, s2);
        int n1 = s1.size();
        int n2 = s2.size();
        int n3 = s3.size();
        if (n1 + n2 != n3)
            return false;
        if (n1 == 0)
            return s2 == s3;
        if (n2 == 0)
            return s1 == s3;
        string key = s1 + "," + s2 + "," + s3;
        if (umap.find(key) != umap.end())
            return umap[key];
        bool match = false;
        if (s1[n1-1] == s3[n3-1] && isInterleave(s1.substr(0, n1-1), s2, s3.substr(0, n3-1)))
            match = true;
        else if (s2[n2-1] == s3[n3-1] && isInterleave(s1, s2.substr(0, n2-1), s3.substr(0, n3-1)))
            match = true;
        umap[key] = match;
        return match;
    }
};