Interleaving String Leetcode Problem 97 [Python Solution]

Question Link: Interleaving String on LeetCode

Problem Overview

The problem of interleaving strings involves determining whether a given string, s3, can be formed by interleaving two other strings, s1 and s2.

An interleaving is a configuration where two strings, s and t, are divided into substrings, such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• The absolute difference between the lengths of s and t is at most 1. The interleaving can be formed by concatenating substrings from s1 and s2, maintaining the relative order of characters.

In other words, the characters in s1 and s2 must appear in s3 in the same order.

Example 1:

Given strings:

• s1 = "aabcc"
• s2 = "dbbca"
• s3 = "aadbbcbcac"

Output: true

Explanation:

One way to obtain s3 is to split s1 into "aa" + "bc" + "c" and s2 into "dbbc" + "a".

Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Given strings:

• s1 = "aabcc"
• s2 = "dbbca"
• s3 = "aadbbbaccc"

Output: false

Explanation:

Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Given strings:

• s1 = ""
• s2 = ""
• s3 = ""

Output: true

This problem can be approached using dynamic programming to optimize the solution.

We will explore both a brute force approach and an efficient approach using dynamic programming.

Understanding Constraints

Before diving into the solution, let's understand the constraints of this problem:

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lowercase English letters.

The constraints indicate that the lengths of the strings involved are relatively small, making it feasible to use dynamic programming for solving this problem efficiently.

Bruteforce Approach

The brute force approach involves exploring all possible combinations of interleaving s1 and s2 and checking if they form s3.

This approach can be implemented using a recursive function.

However, it may result in a significant number of redundant computations, leading to suboptimal time complexity.

Here's a Python code solution for the brute force approach:

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    # Base case: If all strings are empty, we've successfully formed s3. if not s1 and not s2 and not s3:
        return True
    # Check if the characters match between s1 and s3. if s1 and s1[0] == s3[0]:
        if self.isInterleave(s1[1:], s2, s3[1:]):
            return True
    # Check if the characters match between s2 and s3. if s2 and s2[0] == s3[0]:
        if self.isInterleave(s1, s2[1:], s3[1:]):
            return True
    return False

While this brute force approach is conceptually simple, it's not efficient and will result in time complexity exponential in the length of the strings.

Efficient Approach with Dynamic Programming

To optimize the solution, we can use dynamic programming to avoid redundant computations.

We'll create a 2D boolean array dp, where dp[i][j] will indicate whether the first i characters of s1 and the first j characters of s2 can be interleaved to form the first i + j characters of s3.

Here's the Python code for this efficient approach:

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    # Check if the lengths of s1 and s2 add up to the length of s3. if len(s1) + len(s2) != len(s3):
        return False

    # Initialize a 2D DP array to store intermediate results.

dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]

    # Base case: If both strings are empty, we've successfully formed s3. dp[len(s1)][len(s2)] = True

    # Fill in the DP array from bottom to top and right to left.

for i in range(len(s1), -1, -1):
        for j in range(len(s2), -1, -1):
            if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
                dp[i][j] = True
            if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
                dp[i][j] = True

    return dp[0][0]

The dynamic programming approach is more efficient and has a time complexity of O(m * n), where m is the length of s1 and n is the length of s2.

It avoids redundant computations by using the dp array to store intermediate results.

Time and Space Complexity

The time complexity of the efficient dynamic programming solution is O(m * n), where m is the length of s1 and n is the length of s2.

This is because we fill in a 2D DP array of dimensions (m+1) x (n+1).

The space complexity of the solution is also O(m * n) due to the space required for the DP array.

This space complexity is reasonable given the constraints of the problem.

Related Interview Questions By Company:

• Palindrome Partitioning LeetCode
• Permutations II LeetCode
• Remove Nth Node From End Of List LeetCode

Related Interview Questions By Difficulty:

• Count Vowels Permutation LeetCode
• Coin Change II LeetCode
• Last Stone Weight II LeetCode

Related Interview Questions By Category:

• Reverse Integer LeetCode
• Reconstruct Itinerary LeetCode
• Maximal Square LeetCode

Reasoning Behind Our Approach

In the dynamic programming approach, we use a 2D DP array to store intermediate results.

The idea is to iteratively fill in the DP array by checking if, at each position (i, j) in the array, the characters from s1 and s2 can be interleaved to form the characters in s3.

We start from the end of the strings and work our way back to the beginning.

The base case is when both s1 and s2 are empty, and in that case, we've

successfully formed s3.

We initialize dp[len(s1)][len(s2)] to True.

We then iterate through the DP array, filling in values based on whether the characters from s1 and s2 match the corresponding character in s3 and the previous state in the DP array.

The final result is stored in dp[0][0], which indicates whether we can interleave s1 and s2 to form s3.

The approach avoids redundant computations by reusing previously computed results, making it efficient for this problem.