剑指 Offer 19 正则表达式匹配

概述

https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

https://leetcode.com/problems/regular-expression-matching/

这是一道 Hard 哦。

动态规划

为了清晰起见，* 和其之前的值视为整体处理。

注意哦，* 可以是 0 个！

绝了，又是 de 了半天 bug，建议写上注释。

class Solution {
public:
    vector<vector<int>> dp;
    string s, p;
    bool isMatch(string s, string p) {
        this->s = s;
        this->p = p;
        dp.resize(s.size(), vector<int>(p.size(), -1));
        return helper(0, 0);
    }
    
    bool helper(int i, int j) {
        if (i == s.size() && j == p.size()) return true;
        if (j == p.size()) return false;
        if (i == s.size()) {
            while (j < p.size()) {
                if (j + 1 < p.size() && p[j+1] == '*') {
                    j += 2;
                } else {
                    return false;
                }
            }
            return true;
        }
        if (dp[i][j] != -1) return dp[i][j];
        if (j + 1 < p.size() && p[j+1] == '*') {
            if (s[i] == p[j] || p[j] == '.') {
                dp[i][j] = helper(i, j+2) || helper(i+1, j);
            } else {
                dp[i][j] = helper(i, j+2);
            }
        } else {
            if (s[i] == p[j] || p[j] == '.') {
                dp[i][j] = helper(i+1, j+1);
            } else {
                dp[i][j] = 0;
            }
        }
        return dp[i][j];
    }
};

Links: sword-offer-19

未经允许，禁止转载，本文源站链接：https://iamazing.cn/