当前位置：首页 > JavaScript

js实现ismerge

2026-02-01 21:39:28JavaScript

isMerge 实现方法

isMerge 通常指判断一个字符串是否可以由另外两个字符串按顺序合并而成。以下是几种实现方法：

递归方法

递归检查每个字符是否匹配两个字符串中的一个，逐步缩小问题规模。

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

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

动态规划方法

使用动态规划表格记录匹配状态，避免重复计算。

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 && s[i+j-1] === part1[i-1]) dp[i][j] |= dp[i-1][j];
            if (j > 0 && s[i+j-1] === part2[j-1]) dp[i][j] |= dp[i][j-1];
        }
    }
    return dp[part1.length][part2.length];
}

迭代方法

使用指针遍历三个字符串，检查字符匹配情况。

js实现ismerge

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

    let i = 0, j = 0, k = 0;
    while (k < s.length) {
        if (i < part1.length && s[k] === part1[i]) i++;
        else if (j < part2.length && s[k] === part2[j]) j++;
        else return false;
        k++;
    }
    return true;
}