Interleaving String

medium dp strings

Problem

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 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

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];
}

Explanation

We ask whether c can be built by weaving together a and b without reordering either one. The cure for the many possible weavings is a 2-D table that remembers which prefixes can already be matched.

Let dp[i][j] mean "the first i chars of a plus the first j chars of b can form the first i+j chars of c." We seed dp[0][0] = true (empty matches empty). A quick check: if |a| + |b| != |c|, it's instantly false.

To fill a cell, we look at who supplied the last character of c[i+j-1]. Either it came from a — needing a[i-1] == c[i+j-1] and dp[i-1][j] true — or from b — needing b[j-1] == c[i+j-1] and dp[i][j-1] true. If either path works, dp[i][j] is true.

The final cell dp[m][n] tells us whether the whole c is a valid interleaving.

Example: a = "aabcc", b = "dbbca", c = "aadbbcbcac". A path of true cells threads from corner to corner, so the answer is true.

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