We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Interleaving String

Number: 97

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft, Apple, Google, Walmart Labs

Problem Description

Given three strings s1, s2, and s3, determine whether s3 is formed by an interleaving of s1 and s2. An interleaving means that s1 and s2 are divided into substrings and then merged in an alternating order (with a difference of at most one in the number of substrings) to form s3.

Key Insights

  • The problem asks if s3 can be constructed by preserving the order of characters in s1 and s2.
  • A dynamic programming approach is effective by defining dp[i][j] to represent whether s3[0 ... i+j-1] is an interleaving of s1[0 ... i-1] and s2[0 ... j-1].
  • The solution must check that the total lengths match; otherwise, it is immediately false.
  • Transitions are based on whether the current character in s3 matches the next char in s1 or s2.
  • Space optimization to O(s2.length) is possible by reusing a 1D DP array.

Space and Time Complexity

Time Complexity: O(n * m) where n = length of s1 and m = length of s2. Space Complexity: O(n * m) with the basic DP solution. (Can be optimized to O(m) with further space reduction.)

Solution

We use a 2D dynamic programming table where dp[i][j] is true if s3[0 ... i+j-1] can be formed by interleaving s1[0 ... i-1] and s2[0 ... j-1]. First, we check if the lengths of s1 and s2 add up to s3’s length; if not, return false. Then, we initialize dp[0][0] to true and fill in the first row and column based on whether the characters in s2 or s1 correspond to s3. For the rest of the table, dp[i][j] is true if either the previous state dp[i-1][j] is true and s1[i-1] matches s3[i+j-1], or dp[i][j-1] is true and s2[j-1] matches s3[i+j-1]. The answer is found in dp[s1.length][s2.length].

Code Solutions

def isInterleave(s1, s2, s3):
    # Check if the combined lengths of s1 and s2 match s3
    if len(s1) + len(s2) != len(s3):
        return False
    # Initialize dp table with dimensions (len(s1)+1) x (len(s2)+1)
    dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    dp[0][0] = True  # Base case: empty strings form an empty string
    # Fill first row using characters from s2 only
    for j in range(1, len(s2) + 1):
        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
    # Fill first column using characters from s1 only
    for i in range(1, len(s1) + 1):
        dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
    # Fill the rest of the dp table
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 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])
    return dp[len(s1)][len(s2)]

# Example usage:
print(isInterleave("aabcc", "dbbca", "aadbbcbcac"))  # Expected output: True
print(isInterleave("aabcc", "dbbca", "aadbbbaccc"))  # Expected output: False
← Back to All Questions