Interleaving String Check

Problem Statement

Given strings s1, s2, and s3, return true if s3 is formed by interleaving s1 and s2 (keeping each string’s character order).

Example

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

Approach (Dynamic Programming)

Honest note: a greedy two pointer that always consumes a matching character can make a wrong choice when both s1 and s2 match the next character of s3. The correct method is DP: dp[i][j] is true if s3[:i+j] can be formed from s1[:i] and s2[:j].

Complexity

• Time: O(m * n)
• Space: O(n) with a rolling row

Solution Code

Python

def isInterleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(1, n + 1):
        dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
    for i in range(1, m + 1):
        dp[0] = dp[0] and s1[i-1] == s3[i-1]
        for j in range(1, n + 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[n]

Java

boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length();
    if (m + n != s3.length()) return false;
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int j = 1; j <= n; j++)
        dp[j] = dp[j-1] && s2.charAt(j-1) == s3.charAt(j-1);
    for (int i = 1; i <= m; i++) {
        dp[0] = dp[0] && s1.charAt(i-1) == s3.charAt(i-1);
        for (int j = 1; j <= n; 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[n];
}

C++

bool isInterleave(string s1, string s2, string s3) {
    int m = s1.size(), n = s2.size();
    if (m + n != (int)s3.size()) return false;
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int j = 1; j <= n; j++)
        dp[j] = dp[j-1] && s2[j-1] == s3[j-1];
    for (int i = 1; i <= m; i++) {
        dp[0] = dp[0] && s1[i-1] == s3[i-1];
        for (int j = 1; j <= n; j++) {
            dp[j] = (dp[j] && s1[i-1] == s3[i+j-1])
                 || (dp[j-1] && s2[j-1] == s3[i+j-1]);
        }
    }
    return dp[n];
}

Key Takeaways

• Greedy pointer choices can fail — DP explores both options.
• The length check m + n == len(s3) is a necessary first filter.
• A rolling 1D array reduces space from O(m*n) to O(n).