Interleaving String

Hard Subject: 2-D Dynamic Programming

Time Complexity

O(M * N)

Space Complexity

O(M * N)

Problem Description

Problem Statement

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 s = s1 + s2 + ... + sn and t = t1 + t2 + ... + tm, and |n - m| <= 1.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Optimal Solution

Python

Approach: 2-D DP

dp[i][j] is true if s3[0...i+j-1] is an interleaving of s1[0...i-1] and s2[0...j-1]. The recurrence checks if the current char of s3 matches s1 or s2 and if the preceding state in the DP table is valid.

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

        m, n = len(s1), len(s2)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        for i in range(1, m + 1): dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
        for j in range(1, n + 1): dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]

        for i in range(1, m + 1):
            for j in range(1, n + 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[m][n]