Interleaving String

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 they are divided into non-empty substrings such that:

• s = s1 + s2 + ... + sx
• t = t1 + t2 + ... + ty
• |x - y| ≤ 1
• The interleaving is s1 + t1 + s2 + t2 + ... or t1 + s1 + t2 + s2 + ...

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

Examples

Constraints

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

State Transition and Space Optimization

First, if s1.length() + s2.length() != s3.length(), we can immediately return false.

Let dp[i][j] be true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. We can transition to state dp[i][j] from:

• Left: if we match s2[j - 1] with s3[i + j - 1]. Requires dp[i][j - 1] == true and s2[j - 1] == s3[i + j - 1].
• Above: if we match s1[i - 1] with s3[i + j - 1]. Requires dp[i - 1][j] == true and s1[i - 1] == s3[i + j - 1].

Thus: dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])

We can optimize this to a 1D array dp of size s2.length() + 1 by updating it row-by-row.

Solution: 1D DP Array

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length();
        if (n + m != s3.length()) return false;

        boolean[] dp = new boolean[m + 1];

        // base case: empty s1 and empty s2 matches empty s3
        dp[0] = true;

        // initialize the first row (only matching s2 with s3)
        for (int j = 1; j <= m; j++) {
            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        for (int i = 1; i <= n; i++) {
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                     || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        return dp[m];
    }
}

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

        dp = [False] * (m + 1)
        dp[0] = True

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

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

        return dp[m]

#include <vector>
#include <string>

class Solution {
public:
    bool isInterleave(std::string s1, std::string s2, std::string s3) {
        int n = s1.length(), m = s2.length();
        if (n + m != (int)s3.length()) return false;

        std::vector<bool> dp(m + 1, false);
        dp[0] = true;

        for (int j = 1; j <= m; j++) {
            dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1];
        }

        for (int i = 1; i <= n; i++) {
            dp[0] = dp[0] && s1[i - 1] == s3[i - 1];
            for (int j = 1; j <= m; j++) {
                dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1])
                     || (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        }

        return dp[m];
    }
};

Complexity Analysis:

• Time Complexity: O(N * M) where N is the length of s1 and M is the length of s2.
• Space Complexity: O(M) to store the 1D DP array.

← All Problems