js实现ismerge

实现 isMerge 函数

isMerge 函数通常用于判断一个字符串是否可以由另外两个字符串按顺序合并而成。例如，"codewars" 可以由 "cdw" 和 "oears" 合并而成，因为 "c" + "o" + "d" + "w" + "e" + "a" + "r" + "s" 可以组成 "codewars"。

递归方法实现

递归方法通过逐个字符匹配来判断是否可以合并。每次递归调用时，检查当前字符是否与 part1 或 part2 的第一个字符匹配，如果匹配则继续递归。

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

动态规划方法实现

动态规划方法通过构建一个二维数组来记录匹配状态，避免重复计算。dp[i][j] 表示 s 的前 i + j 个字符是否可以通过 part1 的前 i 个字符和 part2 的前 j 个字符合并而成。

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

  const dp = Array.from({ length: part1.length + 1 }, () => 
    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("codewars", "cdw", "oears")); // true
console.log(isMerge("codewars", "cdew", "oars")); // true
console.log(isMerge("codewars", "code", "wars")); // true
console.log(isMerge("codewars", "code", "warss")); // false

注意事项

• 递归方法在字符串较长时可能导致性能问题，因为存在大量重复计算。
• 动态规划方法虽然更高效，但空间复杂度较高，适用于中等长度的字符串。
• 确保输入的 part1 和 part2 的长度之和与 s 的长度一致，否则直接返回 false。