leetcode10：正则表达式匹配

题目链接

leetcode

题目描述

给一个字符串 s 和一个字符规律 p，请你来实现一个支持'.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s，而不是部分字符串。

C++ 代码

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

/*
    暴力解法：递归尝试所有可能的匹配路径，直到找到一个匹配为止。

    递归函数：
        递归函数 matchHelper(s, p, i, j)，
        其中 i 和 j 分别表示字符串 s 和模式 p 的当前索引。
        如果模式 p 已经匹配完，检查字符串 s 是否匹配完。
    处理 *：如果模式的下一个字符是 *，有两种情况：
        * 匹配零次前面的字符：递归调用 matchHelper(s, p, i, j+2)。
        * 匹配多次前面的字符：尝试匹配多个字符，直到不匹配为止。
    普通字符匹配：
        如果当前字符匹配，递归调用 matchHelper(s, p, i+1, j+1)。
    返回结果：
        如果所有路径都尝试过，返回最终结果。

    时间复杂度：O(2^(m+n))
        其中 m 是字符串 s 的长度，n 是模式 p 的长度。
        暴力解法的时间复杂度是指数级 O(2^(m+n))，
        每个字符的匹配有两种选择（匹配或不匹配），* 的存在进一步增加了分支数量。
    空间复杂度：
        由于递归调用栈的深度，空间复杂度为 O(m+n)。
        在最坏情况下，递归调用栈的深度可以达到字符串和模式串的总长度。
*/
class Solution_0 {
public:
    bool isMatch(string s, string p) {
        // 指针 i，j 从索引 0 开始移动
        return matchHelper(s, p, 0, 0);
    }

    bool matchHelper(string& s, string& p, int i, int j) {
        // 结束条件：模式串已经匹配完，检查字符串是否匹配完
        if (j == p.size()) {
            return i == s.size();
        }

        // 模式串的下一个字符是 '*'
        if (j+1 < p.size() && p[j+1] == '*') {
            // '*' 匹配零次前面的字符
            if (matchHelper(s, p, i, j+2)) {
                return true;
            }

            // '*' 匹配多次前面的字符
            while (i < s.size() && (s[i] == p[j] || p[j] == '.')) {
                if (matchHelper(s, p, i+1, j+2)) {
                    return true;
                }
                i++;
            }
        } else {
            // 普通字符匹配
            if (i < s.size() && (s[i] == p[j] || p[j] == '.')) {
                if (matchHelper(s, p, i+1, j+1)) {
                    return true;
                }
            }
        }

        return false;
    }
};

/*
    状态表示：
        f[i][j] 表示 s[1...i] 和 p[1...j] 是否匹配
    状态计算：
        p[j] != '*'
            f[i][j] = f[i-1][j-1] && (s[i] == p[j] || p[j] == '.')
        p[j] == '*',
            f[i][j] = f[i][j-2] || f[i-1][j] && (s[i] == p[j] || p[j] == '.')
            匹配零个字符 
                f[i][j] = f[i][j−2]
            匹配一个或多个字符
                f[i][j] = f[i-1][j] && (s[i] == p[j-1] || p[j-1] == '.')

    时间复杂度：O(mn)
        m 表示 s 的长度，n 表示 p 的长度，总共 mn 个状态，
        状态转移复杂度 O(1)，所以时间复杂度是 O(mn)。
    空间复杂度：O(mn)
        使用了一个大小为 (m+1)*(n+1) 的二维数组 dp，空间复杂度为 O(mn)。
*/
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(m+1, vector<bool>(n+1, false));

        // 初始化
        f[0][0] = true;
        // 处理模式串 p 的匹配符 '*'
        for (int j = 2; j <= n; j++) {
            if (p[j] == '*') {
                f[0][j] = f[0][j-2];
            }
        }

        // 状态计算
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j] != '*') {
                    f[i][j] = f[i-1][j-1] && match(s[i], p[j]);
                } else if (p[j] == '*') {
                    f[i][j] = f[i][j-2] || f[i-1][j] && match(s[i], p[j-1]);
                }
            }
        }

        return f[m][n];
    }

    bool match(char s, char p) {
        return s == p || p == '.';
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = { "aa", "aa", "ab" };
    vector<string> p_cases = { "a", "a*", ".*" };

    for (int i = 0; i < s_cases.size(); i++) {
        string s = s_cases[i];
        string p = p_cases[i];
        bool result = solution.isMatch(s_cases[i], p_cases[i]);

        cout << "Input: s = \"" << s_cases[i] 
        << "\", p = \"" << p_cases[i] << "\"" << endl;
        cout << "Output: " << (result ? "true" : "false") << endl;
    }

    return 0;
}