Is c an Interleaving of a and b

medium dp strings

Problem

Decide whether c can be formed by interleaving the characters of a and b while preserving the internal order of each. The lengths must satisfy |c| = |a| + |b|.

Inputa = "aabcc", b = "dbbca", c = "aadbbcbcac"

Outputtrue

dp[i][j] = c[0..i+j) can be formed by a[0..i) and b[0..j). Transition: dp[i][j] = (dp[i−1][j] && a[i−1] == c[i+j−1]) || (dp[i][j−1] && b[j−1] == c[i+j−1]).

def is_interleave(a, b, c):
    if len(a) + len(b) != len(c): return False
    m, n = len(a), len(b)
    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 a[i-1] == c[i+j-1] and dp[i-1][j]: dp[i][j] = True
            if j > 0 and b[j-1] == c[i+j-1] and dp[i][j-1]: dp[i][j] = True
    return dp[m][n]

function isInterleave(a, b, c) {
  if (a.length + b.length !== c.length) return false;
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => 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 && a[i-1] === c[i+j-1] && dp[i-1][j]) dp[i][j] = true;
      if (j > 0 && b[j-1] === c[i+j-1] && dp[i][j-1]) dp[i][j] = true;
    }
  }
  return dp[m][n];
}

class Solution {
    public boolean isInterleave(String a, String b, String c) {
        if (a.length() + b.length() != c.length()) return false;
        int m = a.length(), n = b.length();
        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 && a.charAt(i-1) == c.charAt(i+j-1) && dp[i-1][j]) dp[i][j] = true;
                if (j > 0 && b.charAt(j-1) == c.charAt(i+j-1) && dp[i][j-1]) dp[i][j] = true;
            }
        }
        return dp[m][n];
    }
}

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

Time: O(|a|·|b|) Space: O(|a|·|b|)