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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Interleaving String

Difficulty: Medium

Problem Description

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 s and t are divided into n and m substrings respectively, such that the interleaving can be formed by alternating characters from s and t.

Key Insights

  • s3 must have a length equal to the sum of the lengths of s1 and s2.
  • Characters from s1 and s2 must appear in the same order in s3 as they do in their respective strings.
  • A dynamic programming approach can be utilized to track the possible interleavings.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s1 and m is the length of s2.
Space Complexity: O(n * m) for the DP table.

Solution

The problem can be solved using dynamic programming by creating a 2D table where the cell dp[i][j] indicates whether s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. The transitions will check if the last character of s3 can be formed by either taking the last character from s1 or s2, ensuring that the respective characters match.

Code Solutions

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    n, m = len(s1), len(s2)
    if n + m != len(s3):
        return False

    # Create a DP table
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # Base case

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

    # Fill the first column
    for i in range(1, n + 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, n + 1):
        for j in range(1, m + 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[n][m]
← Back to All Questions