实现通配符匹配函数的疑问：如何正确处理*的匹配逻辑？

兄弟，这个问题我当初写通配符匹配函数的时候也踩过一模一样的坑！你遇到的核心问题是：单纯从左或从右贪心查找*后的字符，本质是「单一路径匹配」，但*可以匹配任意长度的字符串（包括空），存在多种可能的匹配路径，贪心很容易错过正确的那一条。

先拆解你的两个失败用例 #

• 对于match("a*b", "ababab")：你的左查找逻辑可能找到第一个b就停了，让*匹配了空串，此时pattern的b匹配了expression的第二个字符，但expression还剩abab没处理，所以误判不匹配。但实际上*应该匹配中间的bab，让最后的b对应expression的最后一个字符，这样整个串就匹配成功了。
• 对于match("a*b*b*", "abbbbbbbba")：反向贪心查找时，可能会把倒数第二个b匹配到中间的某个b，导致最后expression剩下的a找不到对应的pattern字符，从而失败。但实际上最后一个*可以匹配空串，倒数第二个b匹配最后一个b，前面的b*匹配中间的所有b，这样就能成功匹配。

解决方案：回溯试探或动态规划 #

要处理*的多可能性匹配，我们需要尝试所有可能的匹配路径，而不是只选一条。这里给你两种常用的实现思路：

方法1：递归回溯（直观易懂）

核心逻辑是：遇到*时，同时尝试两种可能性——要么让*匹配0个字符（直接跳过*，继续匹配pattern的下一个字符），要么让*匹配至少1个字符（保持pattern在*的位置，expression往后移一位）。只要其中一种路径能匹配成功，就返回true。

C语言示例代码：

#include <stdbool.h>

bool matchHelper(char* pattern, char* expr) {
    // 基准情况：两者都到末尾，匹配成功
    if (*pattern == '\0' && *expr == '\0') return true;
    // pattern到末尾但expr还有剩余，不匹配
    if (*pattern == '\0') return false;

    // 当前字符直接匹配，继续往后走
    if (*pattern == *expr) {
        return matchHelper(pattern + 1, expr + 1);
    }

    // 遇到*，尝试两种匹配路径
    if (*pattern == '*') {
        // 路径1：*匹配0个字符，跳过*
        // 路径2：*匹配至少1个字符，expr往后移一位
        return matchHelper(pattern + 1, expr) || matchHelper(pattern, expr + 1);
    }

    // 字符不匹配且不是*，返回false
    return false;
}

bool match(char pattern[], char expression[]) {
    return matchHelper(pattern, expression);
}

不过递归回溯在极端情况下（比如大量*）可能会有重复计算，效率不高，这时候可以用动态规划优化。

方法2：动态规划（高效稳定）

我们用一个二维数组dp[i][j]表示pattern的前i个字符和expression的前j个字符是否匹配，通过状态转移来覆盖所有可能的匹配情况。

状态转移规则：

• 如果pattern[i-1] == expression[j-1]：dp[i][j] = dp[i-1][j-1]（前面匹配的话，当前字符匹配就继续成功）
• 如果pattern[i-1] == '*'：dp[i][j] = dp[i-1][j] || dp[i][j-1]（要么*匹配0个字符，继承i-1的结果；要么*匹配至少1个字符，继承j-1的结果）
• 其他情况：dp[i][j] = false

初始化：

• dp[0][0] = true（空模式匹配空表达式）
• 对于dp[i][0]：只有当pattern的前i个字符全是*时，才为true（因为*可以匹配空串）

C语言示例代码：

#include <stdbool.h>
#include <string.h>

bool match(char pattern[], char expression[]) {
    int len_p = strlen(pattern);
    int len_e = strlen(expression);

    // 创建dp数组，初始化为false
    bool dp[len_p + 1][len_e + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;

    // 处理pattern开头的*，它们可以匹配空串
    for (int i = 1; i <= len_p; i++) {
        if (pattern[i-1] == '*') {
            dp[i][0] = dp[i-1][0];
        }
    }

    // 填充dp数组
    for (int i = 1; i <= len_p; i++) {
        for (int j = 1; j <= len_e; j++) {
            if (pattern[i-1] == expression[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else if (pattern[i-1] == '*') {
                dp[i][j] = dp[i-1][j] || dp[i][j-1];
            }
            // 其他情况保持false，无需额外赋值
        }
    }

    return dp[len_p][len_e];
}

总结一下 #

你之前的贪心思路之所以失败，是因为它只选择了当前看起来最“近”的匹配，但*的匹配需要考虑所有可能的长度。回溯或动态规划通过遍历所有可能的匹配路径，能确保不会漏掉正确的匹配情况，完美解决你遇到的问题。

内容的提问来源于stack exchange，提问作者Aemilius