交错字符串

交错字符串的状态如何定义？

• 问题: 判断 s3 能否由 s1、s2 交错拼接而成, 保持各自字符相对顺序 (97);
• 先决条件: s1.length + s2.length === s3.length, 否则直接为假;
• 状态: dp[i][j] 为 s1 前 i 个字符与 s2 前 j 个字符能否组成 s3 的前 i+j 个字符;
• 初值: dp[0][0] = true;
• 答案: dp[m][n];

转移方程如何写？

• 关键: 看 s3 的末位字符 s3[i+j-1] 来自哪一边;
• 来自 s1: 若 s1[i-1] === s3[i+j-1], 则 dp[i][j] = dp[i-1][j];
• 来自 s2: 若 s2[j-1] === s3[i+j-1], 则 dp[i][j] = dp[i][j] || dp[i][j-1];
• 两条路径只要有一条成立即可;

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

首行首列的初值为什么必须逐个判断？

• 含义: dp[i][0] 表示只用 s1 拼 s3, 只有 s1 的前缀与 s3 完全相同时才为真;

• 做法: 逐字符比较, 一旦不同就 break, 后面全为假;

• 对比: 与 编辑距离 不同, 这里不构造字符, 因此没有"整行都可以转移"的初值;

• 复杂度: 时间 O(mn), 空间 O(mn);