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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        vector<vector<bool>> dp(pattern.size()+1,vector<bool>(str.size()+1,false));
        dp[0][0]=true;
        for(int i=1;i<=pattern.size();i++){
            if(pattern[i-1]=='*'){
                for(int j=1;j<=str.size();j++){
                    if(dp[i-1][j]==true){
                        dp[i][j]=true;
                    }
                    else if(dp[i][j-1]==true&&(str[j-1]==str[j-2]||pattern[i-2]=='.')){
                        dp[i][j]=true;
                    }
                    else{
                        dp[i][j]=false;
                    }
                }
                for(int j=0;j<=str.size();j++){
                    if(dp[i][j]==false){
                        dp[i][j]=dp[i-2][j];
                    }
                }
            }
            else if(pattern[i-1]=='.'){
                for(int j=1;j<=str.size();j++){
                    if(dp[i-1][j-1]==true){
                        dp[i][j]=true;
                    }
                }
            }
            else{
                for(int j=1;j<=str.size();j++){
                    if(dp[i-1][j-1]==true&&str[j-1]==pattern[i-1]){
                        dp[i][j]=true;
                    }
                }
            }
        }
        return dp[pattern.size()][str.size()];
    }
};