题解 | 正则表达式匹配

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    //dp[i][j]表示s的前i个字符和p的前j个字符是否匹配
    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;
       //初始化dp[0][j]
       //只有当出现如a*a*a*这种，才能与空字符串相匹配
       for(int j=2;j<=n;j+=2)
       {
          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]!='*')
            {
                if(pattern[j-1]=='.'||pattern[j-1]==str[i-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
            }
            else 
            {
             char cur=pattern[j-2];
             dp[i][j]=dp[i][j-2];
             if(cur=='.'||cur==str[i-1])
             {
                dp[i][j]=dp[i][j]||dp[i-1][j];
             }
            }
        }
       }
         return dp[m][n];
    }
};