# 正则表达式匹配

###### tags: `競程題解`,`競程`

timestamp：2023/1/22 21:13

[題目連結](https://www.acwing.com/problem/content/30/)

> 這好難QQ 有點類似最短編輯距離的那題，主要都是dp

> 新觀念，好多遞迴dp @@

> 好有趣ww

主要就是，看到這種題目 就是去找出所有case 然後 一定要想到要求的狀態，不然再轉移的部分就直接燒雞

AC扣

class Solution {
public:
    
    int dp[500][500]={};
    
    string s,p;
    bool dfs(int x,int y){
        if(dp[x][y]!=-1) return dp[x][y];
        if(y==(int)p.size()){
            return dp[x][y] = x==s.size(); //一起成立 不用特判 x==s.size();
        }
        bool fm = x<(int)s.size() && (s[x]==p[y]||p[y]=='.');
        bool ans;
        if(y+1<(int)p.size()&&p[y+1]=='*'){
            ans = dfs(x,y+2) || fm && dfs(x+1,y);
        }
        else{
            ans = fm && dfs(x+1,y+1);
        }
        return dp[x][y] = ans;
        
    }
    
    bool isMatch(string _s, string _p) {
        s=_s,p=_p;
        memset(dp,-1,sizeof(dp));
        return dfs(0,0);
    }
};