js实现ismerge

JavaScript 实现 isMerge 函数

isMerge 函数通常用于判断一个字符串是否可以由另外两个字符串按顺序合并而成。例如，"abc" 可以拆分为 "a" 和 "bc" 合并而成，或者 "ab" 和 "c" 合并而成。

递归实现方法

递归方法通过逐步检查字符串的每个字符是否来自两个候选字符串之一：

function isMerge(s, part1, part2) {
  if (s.length !== part1.length + part2.length) {
    return false;
  }

  if (!s.length) {
    return true;
  }

  if (part1.length && s[0] === part1[0] && isMerge(s.slice(1), part1.slice(1), part2)) {
    return true;
  }

  if (part2.length && s[0] === part2[0] && isMerge(s.slice(1), part1, part2.slice(1))) {
    return true;
  }

  return false;
}

动态规划实现方法

动态规划方法通过构建一个二维表格来记录匹配状态：

function isMerge(s, part1, part2) {
  if (s.length !== part1.length + part2.length) {
    return false;
  }

  const dp = Array(part1.length + 1)
    .fill()
    .map(() => Array(part2.length + 1).fill(false));

  dp[0][0] = true;

  for (let i = 0; i <= part1.length; i++) {
    for (let j = 0; j <= part2.length; j++) {
      if (i === 0 && j === 0) {
        continue;
      }

      if (i > 0 && dp[i - 1][j] && s[i + j - 1] === part1[i - 1]) {
        dp[i][j] = true;
      }

      if (j > 0 && dp[i][j - 1] && s[i + j - 1] === part2[j - 1]) {
        dp[i][j] = true;
      }
    }
  }

  return dp[part1.length][part2.length];
}

使用示例

console.log(isMerge("abc", "a", "bc")); // true
console.log(isMerge("abc", "ab", "c"));  // true
console.log(isMerge("abc", "ac", "b"));  // false

注意事项

• 递归方法在字符串较长时可能会导致栈溢出，适合小规模数据。
• 动态规划方法适用于大规模数据，但空间复杂度较高。
• 两种方法的时间复杂度均为 O(n*m)，其中 n 和 m 分别是两个候选字符串的长度。