97. Interleaving String

Description

Given three strings s1, s2, and s3, determine if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s1 and s2 is a valid string that contains all the characters of s1 and s2, and preserves the relative order of characters from both strings.

Intuition

To solve this problem, we can use dynamic programming (DP) to keep track of whether substrings of s3 can be formed by interleaving substrings of s1 and s2. The idea is to use a 2D DP table where each cell dp[i][j] represents whether the substring s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j].

Approach

1. Initial Check: - If the combined length of s1 and s2 is not equal to the length of s3, return false since it's not possible for s3 to be an interleaving.
2. DP Array Initialization: - Create a 2D boolean array dp of size (m+1) x (n+1), where m is the length of s1 and n is the length of s2. Initialize all values to False.
3. Base Case: - Set dp[m][n] to True because an empty s1 and s2 interleave to form an empty s3.
4. Fill the DP Table: - Iterate over the DP table from the end of s1 and s2 to the beginning. - For each position (i, j), check the following: - If the character at s1[i] matches s3[i + j] and the substring starting at s1[i+1] and s2[j] can interleave to form the substring starting at s3[i+j+1], set dp[i][j] to True. - If the character at s2[j] matches s3[i + j] and the substring starting at s1[i] and s2[j+1] can interleave to form the substring starting at s3[i+j+1], set dp[i][j] to True.
5. Return the Result: - The result is stored in dp[0][0], indicating whether s1 and s2 can interleave to form s3. Return this value.

Complexity

Time Complexity:

O(m * n), where m is the length of s1 and n is the length of s2. This is because we need to fill a DP table of size (m+1) x (n+1).

Space Complexity:

O(m * n), for storing the DP table. Each cell in the table is used to store whether a substring can be formed by interleaving.

Code

C++

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

        int m = s1.length(), n = s2.length();
        vector> dp(m + 1, vector(n + 1, false));
        // Base case
        dp[m][n] = true;
        for (int i = m; i >= 0; --i) {
            for (int j = n; j >= 0; --j) {
                if (i < m && s1[i] == s3[i + j] && dp[i + 1][j]) {
                    dp[i][j] = true;
                }
                if (j < n && s2[j] == s3[i + j] && dp[i][j + 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[0][0];
    }
};

Python

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        m, n = len(s1), len(s2)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        # Base case
        dp[m][n] = True
        for i in range(m, -1, -1):
            for j in range(n, -1, -1):
                if i < m and s1[i] == s3[i + j] and dp[i + 1][j]:
                    dp[i][j] = True
                if j < n and s2[j] == s3[i + j] and dp[i][j + 1]:
                    dp[i][j] = True
        return dp[0][0]

Java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        int m = s1.length(), n = s2.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        // Base case
        dp[m][n] = true;
        for (int i = m; i >= 0; --i) {
            for (int j = n; j >= 0; --j) {
                if (i < m && s1.charAt(i) == s3.charAt(i + j) && dp[i + 1][j]) {
                    dp[i][j] = true;
                }
                if (j < n && s2.charAt(j) == s3.charAt(i + j) && dp[i][j + 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[0][0];
    }
}

JavaScript

var isInterleave = function(s1, s2, s3) {
    if (s1.length + s2.length != s3.length) return false;
    var dp = [];
    for(let i = 0; i <= s1.length; i++) {
        dp.push([]);
        for (let j = 0; j <= s2.length; j++) {
            dp[i].push(false)
        }
    }
console.log(dp)
    // base case
    dp[s1.length][s2.length] = true;
    for(let i = s1.length; i >=0; i--) {
        for (let j =s2.length; j>=0; j--) {
            if (i < s1.length && s1[i] == s3[i+j] && dp[i+1][j]) {
                dp[i][j] = true;
            }
            if (j < s3.length && s2[j] == s3[i+j] && dp[i][j+1]) {
                dp[i][j] = true;
            }
        }
    }
    return dp[0][0]
};