题解 | #正则表达式匹配#

class Solution {
public:
   bool match(string str, string pattern) {
        vector<vector<bool>>dp(str.length()+10,vector<bool>(pattern.length()+10,false));
        dp[0][0]=true;
        for(int i=1;i<=pattern.length();i++)if(pattern[i-1]=='*')dp[i][0]=dp[i-2][0];
        for(int i=1;i<=pattern.length();i++)
        for(int j=1;j<=str.length();j++)
        {
            if(pattern[i-1]=='*')
            {
                if(pattern[i-2]=='.')dp[i][j]=true;
                else if(pattern[i-2]==str[j-1])dp[i][j]=dp[i-1][j]||dp[i-1][j-1]||dp[i-2][j];
                else dp[i][j]=dp[i-2][j];
            }
            else if(pattern[i-1]=='.'||str[j-1]==pattern[i-1]) dp[i][j]=dp[i-1][j-1];
        }
        return dp[pattern.length()][str.length()];
    }
};