algoadvance

Given strings s1, s2, and s3, determine 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 the concatenation of the substrings in such a way that maintains the order of the substrings from each string.

Clarifying Questions

1. Are s1, s2, and s3 allowed to contain any type of characters (e.g., letters, digits, symbols)?
   • Yes.
2. Can s1 or s2 be empty?
   • Yes, either can be empty.
3. Is s3 always guaranteed to be longer than or equal to the length of s1 and s2 combined?
   • No, we need to check the length as part of our validation.

Strategy

To solve this problem, we will use dynamic programming. We will create a 2D table dp where dp[i][j] will be True if s3[:i+j] can be formed by interleaving s1[:i] and s2[:j].

Steps:

1. Initialize a table dp where dp[i][j] denotes if s3[:i+j] can be formed by interleaving s1[:i] and s2[:j].
2. Our base case will be dp[0][0] which is True since two empty strings interleave to form an empty string.
3. Populate the table by checking the conditions:
   • If s1[i-1] matches s3[i+j-1], we will check the previous state from s1.
   • If s2[j-1] matches s3[i+j-1], we will check the previous state from s2.
4. Return dp[len(s1)][len(s2)].

Code

Here is the Python code to solve the problem:

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    # If the length of s3 isn't equal to the length of s1 plus s2, return False
    if len(s3) != len(s1) + len(s2):
        return False
    
    # Initialize the DP table
    dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    dp[0][0] = True
    
    # Fill the first row
    for j in range(1, len(s2) + 1):
        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
    
    # Fill the first column
    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
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
print(isInterleave(s1, s2, s3))  # Output: True

Time Complexity

• Time Complexity: The solution has a time complexity of (O(n \times m)), where (n) is the length of s1 and (m) is the length of s2. This is because we are filling a 2D table of size n x m.
• Space Complexity: The space complexity is also (O(n \times m)) due to the storage required for the 2D table.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?