剑指 Offer 19 正则表达式匹配

标签: 剑指 Offer 发布于:2022-02-28 11:57:15 编辑于:2022-02-28 12:33:17 浏览量:395

概述

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];
    }
};

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