如何用C++实现支持通配符*和?的字符串匹配算法 递归与动态规划思路详解

通配符匹配是字符串处理场景中非常实用的功能，其中*可以匹配零个或多个任意字符，?可以匹配恰好一个任意字符。在C++中实现这类匹配算法，常见的思路有递归和动态规划两种，下面分别展开讲解。

递归思路实现

递归的核心思想是逐个对比字符串和通配符的字符，根据当前字符的类型决定下一步的匹配逻辑。首先处理边界情况：如果通配符已经遍历完，那么只有字符串也遍历完才匹配成功；如果字符串遍历完但通配符还有剩余，只有剩余的都是*才可能匹配成功。

接下来分情况处理当前字符：

• 如果当前通配符字符是?，那么直接匹配字符串的当前字符，同时移动两个指针
• 如果当前通配符字符是*，有两种选择：一是*匹配零个字符，移动通配符指针；二是*匹配至少一个字符，移动字符串指针
• 如果当前通配符字符是普通字符，那么只有两者相等时才同时移动指针，否则匹配失败

下面是递归实现的完整源码：

#include <iostream>
#include <string>
using namespace std;

// 递归匹配函数，s为待匹配字符串，p为通配符模式，sIdx和pIdx分别为当前遍历位置
bool matchRecursive(const string& s, const string& p, int sIdx, int pIdx) {
    // 通配符遍历完，只有字符串也遍历完才匹配成功
    if (pIdx == p.size()) {
        return sIdx == s.size();
    }
    // 字符串遍历完，只有剩余通配符都是*才可能匹配成功
    if (sIdx == s.size()) {
        for (int i = pIdx; i < p.size(); ++i) {
            if (p[i] != '*') {
                return false;
            }
        }
        return true;
    }
    // 当前通配符是?，直接匹配一个字符
    if (p[pIdx] == '?') {
        return matchRecursive(s, p, sIdx + 1, pIdx + 1);
    }
    // 当前通配符是*，两种选择：匹配0个字符或者匹配1个字符
    if (p[pIdx] == '*') {
        // *匹配0个字符，移动通配符指针
        if (matchRecursive(s, p, sIdx, pIdx + 1)) {
            return true;
        }
        // *匹配1个字符，移动字符串指针
        return matchRecursive(s, p, sIdx + 1, pIdx);
    }
    // 普通字符，必须相等才继续匹配
    if (s[sIdx] == p[pIdx]) {
        return matchRecursive(s, p, sIdx + 1, pIdx + 1);
    }
    return false;
}

// 对外暴露的匹配接口
bool isMatch(const string& s, const string& p) {
    return matchRecursive(s, p, 0, 0);
}

int main() {
    // 测试用例
    cout << isMatch("abc", "a?c") << endl;  // 输出1，匹配成功
    cout << isMatch("abc", "a*") << endl;   // 输出1，匹配成功
    cout << isMatch("abc", "a?d") << endl;  // 输出0，匹配失败
    return 0;
}

动态规划思路实现

递归实现虽然逻辑清晰，但是存在大量的重复子问题，时间复杂度较高。动态规划通过记录子问题的结果来避免重复计算，效率更高。我们定义二维数组dp[i][j]表示字符串前i个字符和通配符前j个字符是否匹配。

状态转移逻辑如下：

• 初始化dp[0][0]为true，表示空字符串和空模式匹配
• 处理通配符开头是*的情况，dp[0][j]只要前面都是*就为true
• 遍历字符串和通配符的每个位置：
  • 如果通配符当前字符是?，那么dp[i][j] = dp[i-1][j-1]
  • 如果通配符当前字符是*，那么dp[i][j] = dp[i][j-1] || dp[i-1][j]，分别表示*匹配0个字符和*匹配多个字符
  • 如果是普通字符，那么dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1]

下面是动态规划实现的完整源码：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool isMatch(const string& s, const string& p) {
    int sLen = s.size();
    int pLen = p.size();
    // dp[i][j]表示s的前i个字符和p的前j个字符是否匹配
    vector<vector<bool>> dp(sLen + 1, vector<bool>(pLen + 1, false));
    // 空字符串和空模式匹配
    dp[0][0] = true;
    // 处理通配符开头是*的情况
    for (int j = 1; j <= pLen; ++j) {
        if (p[j-1] == '*') {
            dp[0][j] = dp[0][j-1];
        } else {
            break;
        }
    }
    // 遍历填充dp数组
    for (int i = 1; i <= sLen; ++i) {
        for (int j = 1; j <= pLen; ++j) {
            if (p[j-1] == '?') {
                // ?匹配单个字符
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] == '*') {
                // *匹配0个或多个字符
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            } else {
                // 普通字符必须相等
                dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1]);
            }
        }
    }
    return dp[sLen][pLen];
}

int main() {
    // 测试用例
    cout << isMatch("abc", "a?c") << endl;  // 输出1，匹配成功
    cout << isMatch("abc", "a*") << endl;   // 输出1，匹配成功
    cout << isMatch("abc", "a?d") << endl;  // 输出0，匹配失败
    return 0;
}

两种思路对比

实际开发中更推荐使用动态规划实现，时间和空间效率都更稳定，能够应对更长的字符串和通配符模式匹配需求。

C++字符串匹配通配符匹配递归动态规划修改时间：2026-07-22 00:06:24