题目描述

blablabla

样例

blablabla

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