Interleaving String

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size();
        if (n + m != (int)s3.size()) return false;
        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];
    }
};

func isInterleave(s1 string, s2 string, s3 string) bool {
    n, m := len(s1), len(s2)
    if n+m != len(s3) {
        return false
    }
    dp := make([]bool, m+1)
    dp[0] = true
    for j := 1; j <= m; j++ {
        dp[j] = dp[j-1] && s2[j-1] == s3[j-1]
    }
    for i := 1; i <= n; i++ {
        dp[0] = dp[0] && s1[i-1] == s3[i-1]
        for 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]
}

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]

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

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];
        dp[0] = true;
        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];
    }
}

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