Intuition

Let dp[i][j] mean the first i chars of s1 and first j of s2 can interleave to form the first i+j chars of s3. Each step consumes one char from s1 or s2 if it matches the next char of s3.

Approach

If lengths do not add up, return false.
dp[0][0] = true. dp[i][j] is true if (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1]).
Answer is dp[m][n].

Complexity

Time — O(m*n): fill the table once.
Space — O(m*n): the DP grid (reducible to O(n)).

Common Pitfalls

A greedy char-by-char match fails; you need the full DP because either string could supply the next char.

Full Solution — all languages

class Solution:
    def isInterleave(self, s1, s2, s3):
        m,n=len(s1),len(s2)
        if m+n!=len(s3): return False
        dp=[[False]*(n+1) for _ in range(m+1)]
        dp[0][0]=True
        for i in range(m+1):
            for j in range(n+1):
                if i>0 and s1[i-1]==s3[i+j-1] and dp[i-1][j]: dp[i][j]=True
                if j>0 and s2[j-1]==s3[i+j-1] and dp[i][j-1]: dp[i][j]=True
        return dp[m][n]

import java.util.*;

class Solution {
    public 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[m+1][n+1]; dp[0][0]=true; for(int i=0;i<=m;i++)for(int j=0;j<=n;j++){if(i>0&&s1.charAt(i-1)==s3.charAt(i+j-1)&&dp[i-1][j])dp[i][j]=true;if(j>0&&s2.charAt(j-1)==s3.charAt(i+j-1)&&dp[i][j-1])dp[i][j]=true;} return dp[m][n];
    }
}

#include <bits/stdc++.h>
using namespace std;

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

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    const m=s1.length,n=s2.length; if(m+n!==s3.length)return false; const dp=[]; for(let i=0;i<=m;i++)dp.push(new Array(n+1).fill(false)); dp[0][0]=true; for(let i=0;i<=m;i++)for(let j=0;j<=n;j++){if(i>0&&s1[i-1]===s3[i+j-1]&&dp[i-1][j])dp[i][j]=true;if(j>0&&s2[j-1]===s3[i+j-1]&&dp[i][j-1])dp[i][j]=true;} return dp[m][n];
};

Interleaving String

Example 1

Example 2

Constraints