Interleaving String - Leetcode Solution

Problem Statement:

Given strings s1, s2, and s3, return true if 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 s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Explanation: One possible interleaving of s1 and s2 is "aabccdbbcaaac".

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

Solution:

We can easily solve this problem using dynamic programming. We can define dp[i][j] as True if s3[0:i+j] is an interleaving of s1[0:i] and s2[0:j].

The base case for our dp table is dp[0][0] = True, which indicates that an empty string is an interleaving of two empty strings.

Now, we need to fill the remaining cells of the dp table. For this, we can iterate through the indices i and j of s1 and s2 respectively and check if s3[i+j-1] matches either s1[i-1] or s2[j-1].

If s3[i+j-1] matches s1[i-1], then dp[i][j] = dp[i-1][j]. This is because we can just use the current character from s1 and skip a character in s3.

Similarly, if s3[i+j-1] matches s2[j-1], then dp[i][j] = dp[i][j-1], because we can use the current character from s2 and skip a character in s3.

If s3[i+j-1] doesn't match either s1[i-1] or s2[j-1], then dp[i][j] is False because we cannot form s3 from s1 and s2 using the current characters.

Finally, the answer to our problem is stored in the dp[n1][n2], where n1 and n2 are the lengths of s1 and s2 respectively.

Now, let's see the Python implementation of the above algorithm.

Python Code:

def isInterleave(s1: str, s2: str, s3: str) -> bool: n1, n2, n3 = len(s1), len(s2), len(s3)

# dp[i][j] is True if s3[0:i+j] is an interleaving of s1[0:i] and s2[0:j]
dp = [[False] * (n2+1) for _ in range(n1+1)]
dp[0][0] = True

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

# fill the first column
for i in range(1, n1+1):
    dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]

# fill the remaining cells
for i in range(1, n1+1):
    for j in range(1, n2+1):
        k = i + j - 1
        dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[k]) or \
                   (dp[i][j-1] and s2[j-1] == s3[k])

return dp[n1][n2]

The time complexity of the above algorithm is O(n1n2), where n1 and n2 are the lengths of s1 and s2 respectively. And the space complexity is also O(n1n2), which is used to store the dp table.

So, this is the detailed solution of the Interleaving String problem on LeetCode.

1