交错字符串

二 题目

给定三个字符串 s1, s2, s3,
验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/interleaving-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

动态规划：

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
const isInterleave = (s1, s2, s3) => {
  const n = s1.length,
    m = s2.length,
    t = s3.length;
  if (n + m !== t) {
    return false;
  }

  const f = Array.from(Array(n + 1), () => Array.from(Array(m + 1), () => false));

  f[0][0] = true;
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= m; j++) {
      const p = i + j - 1;
      if (i > 0) {
        f[i][j] = f[i][j] || (f[i - 1][j] && s1[i - 1] === s3[p]);
      }
      if (j > 0) {
        f[i][j] = f[i][j] || (f[i][j - 1] && s2[j - 1] === s3[p]);
      }
    }
  }
  
  return f[n][m];
};

console.log(isInterleave(
  'aabcc',
  'dbbca',
  'aadbbcbcac',
)); // true

动态规划之滚动数组

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
const isInterleave = (s1, s2, s3) => {
  const n = s1.length,
    m = s2.length,
    t = s3.length;
  if (n + m !== t) {
    return false;
  }

  const f = Array.from(Array(n + 1), () => false);

  f[0] = true;
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= m; j++) {
      const p = i + j - 1;
      if (i > 0) {
        f[j] &= (s1[i - 1] === s3[p]);
      }
      if (j > 0) {
        f[j] |= (f[j - 1] && s2[j - 1] === s3[p]);
      }
    }
  }

  return f[m];
};

console.log(isInterleave(
  'aabcc',
  'dbbca',
  'aadbbcbcac',
)); // true

四 统计分析

本题不需要统计分析。

五 套路分析

如果小伙伴有更好的思路想法，或者没看懂其中某种解法，欢迎评论留言或者私聊 jsliang~

---

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。