题解 | 正则表达式匹配

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        int  m = str.size();
        int n = pattern.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        dp[0][0] = true;
        for(int j=2;j<=n;j++){
            if(pattern[j-1] == '*'){
                dp[0][j] = dp[0][j-2];
            }
        }
        for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){
            if(pattern[j-1]!='*' && str[i-1]==pattern[j-1] || pattern[j-1]=='.'){
                dp[i][j] = dp[i-1][j-1];
            }else if(pattern[j-1]!='*'&& str[i-1]!=pattern[j-1] && pattern[j-1]!='.'){
                dp[i][j] = false;
            }else if(j>=2 && pattern[j-1] =='*'){
                if(pattern[j-2]==str[i-1] || pattern[j-2]=='.'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-2];//dp[i][j] = dp[i-1][j]表示多复制一个//等于dp[i][j-2]表示删掉当前的pattern[j-1]和pattern[j-2]
                }else{
                    dp[i][j] = dp[i][j-2];//不匹配就把这pattern[j-1]和pattern[j-2]删掉
                }
            }
        }
        return dp[m][n];

    }
};