動的計画法で 2 つの文字列を順を保って混ぜると 3 つ目になるか調べる

def can_interleave(a, b, c):
    m, n = len(a), len(b)
    if m + n != len(c):
        return False
    a, b = " " + a, " " + b
    ok = [False] * (n + 1)
    for i in range(m + 1):
        for j in range(n + 1):
            if i == j == 0:
                ok[j] = True
                continue
            ch = c[i + j - 1]
            up = i > 0
            up &= ok[j]
            up &= a[i] == ch
            left = j > 0
            left &= ok[j - 1]
            left &= b[j] == ch
            ok[j] = up or left
    return ok[n]

function canInterleave(
  a, b, c,
) {
  const m = a.length;
  const n = b.length;
  if (m + n !== c.length) {
    return false;
  }
  const ok = Array(n + 1)
    .fill(false);
  for (let i = 0; i <= m; i++) {
    for (const j of ok.keys()) {
      if (i + j === 0) {
        ok[j] = true;
        continue;
      }
      const ch = c[i + j - 1];
      const up = i > 0
        && ok[j]
        && a[i - 1] === ch;
      const left = j > 0
        && ok[j - 1]
        && b[j - 1] === ch;
      ok[j] = up || left;
    }
  }
  return ok[n];
}

func canInterleave(
	a, b, c string,
) bool {
	m, n := len(a), len(b)
	if m+n != len(c) {
		return false
	}
	ok := make([]bool, n+1)
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			if i+j == 0 {
				ok[j] = true
				continue
			}
			ch := c[i+j-1]
			up := i > 0 && ok[j] &&
				a[i-1] == ch
			left := j > 0 &&
				ok[j-1] && b[j-1] == ch
			ok[j] = up || left
		}
	}
	return ok[n]
}