Interleaving String 🧠

LeetCode Link: Interleaving String

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 97 - Interleaving String

Description: Given strings s1, s2, and s3, find whether s3 is formed by the interleaving of s1 and s2.

Intuition: To determine if s3 can be formed by interleaving s1 and s2, we can use dynamic programming. The problem can be broken down into smaller subproblems, where we check if a prefix of s3 can be formed by interleaving prefixes of s1 and s2.

Approach:

1. Create a 2D dp array of size (s1.length()+1) x (s2.length()+1), where dp[i][j] represents whether s3[0...i+j-1] can be formed by interleaving s1[0...i-1] and s2[0...j-1].
2. Initialize dp[0][0] as true, representing the base case where both s1 and s2 are empty, and s3 is also empty.
3. Fill in the dp array using the following recurrence relation:

• dp[i][j] is true if one of the following conditions is met:
• dp[i-1][j] is true, and s1[i-1] is equal to s3[i+j-1].
• dp[i][j-1] is true, and s2[j-1] is equal to s3[i+j-1].

4. Return dp[s1.length()][s2.length()], which represents whether s3 can be formed by interleaving s1 and s2.

⌛ Time Complexity: The time complexity is O(s1.length() * s2.length()), as we fill in the entire dp array.

💾 Space Complexity: The space complexity is O(s1.length() * s2.length()), as we use a 2D array to store the intermediate results.

Dynamic Programming:

• Subproblem: The subproblem is checking if a prefix of s3 can be formed by interleaving prefixes of s1 and s2.
• Recurrence Relation: dp[i][j] is true if dp[i-1][j] is true and s1[i-1] is equal to s3[i+j-1], or if dp[i][j-1] is true and s2[j-1] is equal to s3[i+j-1].
• Base Case: Initialize dp[0][0] as true, representing the base case where both s1 and s2 are empty, and s3 is also empty.

Solutions 💡

Cpp 💻

class Solution {
  public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length(), n = s2.length();

        // If the lengths of s1 and s2 do not add up to the length of s3, it's not possible to form s3 by interleaving s1 and s2
        if (m + n != s3.length()) {
            return false;
        }

        // Create a 2D dp array to store the results of subproblems
        // dp[i][j] represents whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        // Base case: Both s1 and s2 are empty, and the result is true
        dp[0][0] = true;

        // Loop through each possible combination of i and j
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                // Check if the previous characters of s1 and s3 match
                if (i > 0 && s1[i - 1] == s3[i + j - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }

                // Check if the previous characters of s2 and s3 match
                if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
                }
            }
        }

        // Return the result, whether the last characters of s1 and s2 can form the last characters of s3
        return dp[m][n];
    }
};

Python 🐍

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Get the lengths of s1, s2, and s3.
        m, n, p = len(s1), len(s2), len(s3)

        # If the sum of lengths of s1 and s2 is not equal to the length of s3, return False.
        if m + n != p:
            return False

        # Initialize a 2D DP array dp of size (m + 1) x (n + 1) to store intermediate results.
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: dp[0][0] is True since two empty strings can form an empty string.
        dp[0][0] = True

        # Fill in the first row of dp.
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

        # Fill in the first column of dp.
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

        # Fill in the rest of dp.
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # For dp[i][j] to be True, one of the following conditions must be met:
                # 1. dp[i-1][j] is True and s1[i-1] matches s3[i+j-1].
                # 2. dp[i][j-1] is True and s2[j-1] matches s3[i+j-1].
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (
                    dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
                )

        # The result is stored in dp[m][n].
        return dp[m][n]