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

定义dp:dp(s,i,p,j)=ture 表示s[i...]可以匹配p[j...]； 若dp(s,i,p,j)=false 则表示s[i...]不可以匹配p[j...]。 根据定义i=0, j=0为我们想要的结果。

如果不考虑p[j+1]='*'，那么当s[i] ==p[j]（或p[j]=='.'）时，i++,j++就好；s[i]!=p[j]时，直接return false。

然而，无论是s[i] ==p[j]还是s[i]!=p[j]都会面临p[j+1]为*的问题。 当s[i] ==p[j]（或p[j]=='.'）时，有两种情况：

1)p[j]可能匹配多次（s="aaa", p="a*"），p[j]匹配了s[i]，但是p[j]还需要继续匹配s[i]后的字符，此时，j不变，i++;

2)p[j]匹配0次（s="aaa", p="b*aa"）,此时我们需要看s[i]与p[j+2]的情况(直接跳过p[j]字符和*)，此时i不变，j++;

代码详情如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    unordered_map<string, bool> memo;
    bool dp(string& s, int i, string& p, int j){
        int m = s.size();
        int n = p.size();
        // parttern 匹配到头了
        if(j==n){
            //s必须到头才为true
            return i==m;
        }
        if(i==m){
            //判断是不是x*y*z*的情况
            if((n-j)%2 ==1) return false; //此情况必须偶数个数量
            
            for(;j+1<n;j+=2){
                if(p[j+1]!='*') return false; 
            }
            return true;
        }
        
        // 剪枝 如果已经出现过，就不再递归
        string tmp = to_string(i)+","+to_string(j);
        if(memo.count(tmp)) return memo[tmp];
        
        bool res = false;
        //相等于不相等都要判断pattern下一个是否为*
        // 相等
        if(s[i]==p[j] || p[j]=='.'){
            if(j<n-1 && p[j+1] == '*'){
                res = dp(s, i, p, j+2) || dp(s, i+1, p, j); //parttern中*前面的字符出现可能是 0次或者 多次
            }
            else
                res = dp(s, i+1, p, j+1); //正常匹配
        }
        //不相等
        else{
            if(j<n-1 && p[j+1] == '*')
                res = dp(s, i, p, j+2);   //parttern中*前面的字符只能是出现是0次
            else
                res = false; //不匹配
        }
        memo[tmp] = res;
        return res;
    }
    bool match(string str, string pattern) {
        // write code here
  
        return dp(str, 0, pattern, 0);
    }
};

动态规划的时间复杂度=状态组合*每次递归的花费时间 时间复杂度和空间复杂度都为o(MN)