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

解题思路参考leetcode10.

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    //判断str的第i个字符和pattern的第j个字符是否匹配，i,j从1开始
    bool char_match(string str,string pattern,int i,int j){
        if(i==0) return false;
        if(pattern[j-1]=='.') return true;
        return str[i-1]==pattern[j-1];
    }
    
    bool match(string str, string pattern) {
        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 i=0;i<=m;i++){
            for(int j=1;j<=n;j++)
                if(pattern[j-1]=='*'){
                    dp[i][j]=dp[i][j] || dp[i][j-2];
                    if(char_match(str, pattern, i, j-1)) dp[i][j]=dp[i][j] || dp[i-1][j];
                }
                else{
                    if(char_match(str, pattern, i, j)) dp[i][j]=dp[i][j] || dp[i-1][j-1];
                }
        }
        return dp[m][n];
    }
};