45. 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

Solution: (Recursion)

class Solution
{
public:
    bool isValid(string s1, string s2, string s3, string res, int i, int j, vector<vector<int>> &dp)
    {

        if (res == s3 && i == s1.length() && j == s2.length())
        {
            return true;
        }

        if (res.length() >= s3.length())
        {
            return false;
        }

        bool x = false, y = false;

        if (i < s1.length())
        {
            x = isValid(s1, s2, s3, res + s1[i], i + 1, j, dp);
        }
        if (j < s2.length())
        {
            y = isValid(s1, s2, s3, res + s2[j], i, j + 1, dp);
        }

        bool ans = x || y;
        return ans;
    }

    bool isInterleave(string s1, string s2, string s3)
    {
        int n = s1.length();
        int m = s2.length();
        vector<vector<int>> dp(n+1, vector<int>(m+1, -1));

        if (isValid(s1, s2, s3, "", 0, 0, dp))
        {
            return true;
        }

        return false;
    }
};

Time Complexity: (2^ (m+n) )

Solution: (Memonization)

class Solution
{
public:
    unordered_map<string, bool> m;

    bool createString(string &s1, string &s2, string &s3, string res, int i, int j, int k)
    {
        if (res.length() == s3.length())
        {
            if (i == s1.length() && j == s2.length() && res == s3)
            {
                return true;
            }
        }

        if (res.length() >= s3.length())
        {
            return false;
        }

        string key = to_string(i) + '*' + to_string(j) + '*' + to_string(k);

        if (m.find(key) != m.end())
        {
            return m[key];
        }

        bool x = false, y = false;

        if (i < s1.length() && s1[i] == s3[k])
        {
            x = createString(s1, s2, s3, res + s1[i], i + 1, j, k + 1);
        }

        if (j < s2.length() && s2[j] == s3[k])
        {
            y = createString(s1, s2, s3, res + s2[j], i, j + 1, k + 1);
        }

        m[key] = x || y;
        return m[key];
    }

    bool isInterleave(string s1, string s2, string s3)
    {
        return createString(s1, s2, s3, "", 0, 0, 0);
    }
};

Solution: (DP)

class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {

        int n = s1.length();
        int m = s2.length();
        int k = s3.length();

        if ((n + m) != k)
        {
            return false;
        }

        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));

        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= m; j++)
            {

                if (i == 0 && j == 0)
                {
                    dp[i][j] = true;
                }
                //Case 1: s1 is null
                else if (i == 0)
                {
                    dp[i][j] = s2[j - 1] == s3[i + j - 1] && dp[i][j - 1];
                }
                 //Case 2: s2 is null
                else if (j == 0)
                {
                    dp[i][j] = s1[i - 1] == s3[i + j - 1] && dp[i - 1][j];
                }
                // Case 3: Checking others
                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[n][m];
    }
};

Time Complexity: O(n * m)