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

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching

---

这里不考虑嵌套的闭包，因此设计状态 (i,j)，考虑三种转移（匹配、跳出闭包、重复闭包），BFS 即可

class Solution {
public:
    bool isMatch(string s, string p) {
        int n=s.length();
        int m=p.length();
        queue<pair<int,int>> que;
        vector<vector<int>> vis(n+2,vector<int>(m+2));
        que.push({0,0});
        vis[0][0]=1;
        auto checkValid=[&](int i,int j)->bool {
            return i>=0 && i<=n && j>=0 && j<=m;
        };
        auto pushState=[&](int i,int j)->void {
            if(!checkValid(i,j)) return;
            if(vis[i][j]==true) return;
            vis[i][j]=true;
            que.push({i,j});
        };
        while(!que.empty())
        {
            auto [i,j]=que.front();
            que.pop();
            if(i==n&&j==m) return true;
            if(j==m) continue;
            if(i<n && s[i]==p[j] || p[j]=='.') 
            {
                pushState(i+1,j+1);
            }
            if(j+1<m && p[j+1]=='*')
            {
                pushState(i,j+2);
            }
            if(j>0 && p[j]=='*')
            {
                pushState(i,j-1);
            }
        }
        return false;
    }
};