[44] 通配符匹配

动态规划（DP）解法：

details

  1. 定义 DP 数组：

    • 定义 dp[i][j] 表示 s[0:i] 与 p[0:j] 是否匹配。
    • dp[i][j] = true 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是匹配的。

  2. 状态转移：

    • 如果 p[j-1] == ? 或 p[j-1] == s[i-1]，则当前字符匹配，状态转移为 dp[i][j] = dp[i-1][j-1]。
    • 如果 p[j-1] == *，则星号可以匹配零个或多个字符，状态转移有两种可能：
      • dp[i][j] = dp[i-1][j]，表示 * 匹配了 s[i-1]；
      • dp[i][j] = dp[i][j-1]，表示 * 匹配了空字符。

  3. 初始条件：

    • dp[0][0] = true，表示空字符串与空模式是匹配的。
    • 当 i == 0 时，即空字符串与模式 p 匹配，只有当模式 p 仅包含 * 时，才能匹配空字符串。

  4. 结果：

    • dp[m][n] 表示 s[0:m] 和 p[0:n] 的匹配情况，最终返回这个值。

代码实现（JavaScript）：

function isMatch(s, p) {
    const m = s.length;
    const n = p.length;

    // 初始化 dp 数组
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    dp[0][0] = true; // 空字符串和空模式匹配

    // 初始化 p 的前缀是 '*' 的情况
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    // 填充 dp 表
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
    }

    return dp[m][n];
}

// 示例
console.log(isMatch('adceb', '*a*b')); // 输出 true
console.log(isMatch('acdcb', 'a*c?b')); // 输出 false

解释：

  1. 初始条件：

    • dp[0][0] = true，表示空字符串和空模式匹配。
    • 处理 dp[0][j]，表示空字符串和模式匹配，如果模式前 j 个字符都是 *，则匹配成功。

  2. 状态转移：

    • 当 p[j-1] == ? 或 p[j-1] == s[i-1] 时，说明当前字符匹配，状态继承自 dp[i-1][j-1]。
    • 当 p[j-1] == * 时，可以有两种选择：
      • dp[i-1][j] 表示 * 匹配多个字符。
      • dp[i][j-1] 表示 * 匹配空字符。

  3. 结果：

    • 最终返回 dp[m][n]，表示整个字符串 s 是否与模式 p 匹配。

复杂度分析：

  • 时间复杂度：O(m * n)，其中 m 是字符串 s 的长度，n 是模式 p 的长度，需要遍历 dp 表的所有元素。
  • 空间复杂度：O(m * n)，因为使用了 dp 二维数组。

贪心算法解法：

details

使用 贪心算法 来解决“44. 通配符匹配”问题时，我们主要关注 * 通配符的处理。通配符 * 可以匹配任意长度的字符序列，甚至是空字符串。基于这一点，我们可以通过贪心策略实现模式匹配。

贪心算法解法步骤：

  1. 遍历字符串 s 和模式 p，逐个字符检查是否匹配：

    • 当 p[j] == s[i] 或 p[j] == '?' 时，字符匹配，继续比较下一个字符。
    • 当 p[j] == '*' 时，记录下当前 * 所在的位置，并尝试让 * 先匹配空字符，然后继续检查后续字符。
    • 如果发现后续字符不匹配，可以回溯到 * 的位置，让 * 匹配更多字符。

  2. 回溯策略：

    • 如果匹配到模式中的 *，先假设 * 匹配空字符串。如果之后发现字符不匹配，则让 * 回溯，尝试匹配更多字符。

  3. 边界条件：

    • 匹配结束后，模式中剩余的字符必须全是 *，否则无法完全匹配。

代码实现（JavaScript）：

function isMatch(s, p) {
    let sLen = s.length,
        pLen = p.length;
    let sIdx = 0,
        pIdx = 0;
    let starIdx = -1,
        sTmpIdx = -1;

    while (sIdx < sLen) {
        // 1. 匹配 '?' 或者字符相同
        if (pIdx < pLen && (p[pIdx] === '?' || p[pIdx] === s[sIdx])) {
            sIdx++;
            pIdx++;
        }
        // 2. 遇到 '*'，记录 '*' 的位置，假设它匹配空字符串
        else if (pIdx < pLen && p[pIdx] === '*') {
            starIdx = pIdx;
            sTmpIdx = sIdx;
            pIdx++;
        }
        // 3. 当前字符不匹配，但之前有 '*'，尝试回溯
        else if (starIdx !== -1) {
            pIdx = starIdx + 1; // 回溯到 '*' 的下一个字符
            sTmpIdx++; // 让 '*' 匹配多一个字符
            sIdx = sTmpIdx; // 更新 s 的索引
        }
        // 4. 当前字符不匹配且没有 '*'，匹配失败
        else {
            return false;
        }
    }

    // 检查模式串 p 剩余的部分是否全为 '*'
    while (pIdx < pLen && p[pIdx] === '*') {
        pIdx++;
    }

    // 如果 pIdx 到达了模式串末尾，则匹配成功
    return pIdx === pLen;
}

// 示例
console.log(isMatch('adceb', '*a*b')); // 输出 true
console.log(isMatch('acdcb', 'a*c?b')); // 输出 false

解释：

  1. 初始化：

    • sIdx 和 pIdx 分别是遍历字符串 s 和模式 p 的指针。
    • starIdx 记录最近一次出现 * 的位置。
    • sTmpIdx 记录匹配 * 时字符串 s 中的指针位置。

  2. 主循环：

    • 当字符 p[pIdx] == s[sIdx] 或 p[pIdx] == '?' 时，直接匹配字符，继续移动两个指针。
    • 当遇到 * 时，记录 * 在 p 中的位置 starIdx 和 s 中的位置 sTmpIdx，并继续匹配模式中的下一个字符（假设 * 暂时匹配空字符串）。
    • 如果字符不匹配，但之前出现过 *，就尝试让 * 多匹配一个字符（回溯到 * 位置）。

  3. 检查模式串尾部：

    • 匹配结束后，如果模式串 p 还剩下一些字符，必须确保它们全是 *，否则无法匹配。

复杂度分析：

  • 时间复杂度：O(m + n)，其中 m 是字符串 s 的长度，n 是模式 p 的长度。我们在匹配过程中最多遍历 s 和 p 各一次，贪心算法的效率较高。
  • 空间复杂度：O(1)，仅使用了固定数量的指针和变量，没有使用额外的空间。
Last Updated:
Contributors: rosendo