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

动态规划，详细注释在代码中了

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        //dp[i][j] 表示str前i个字符和pattern前j个字符的匹配情况
        int n=str.size();
        int m=pattern.size();
        vector> dp(n+1,vector(m+1,false));

        //方便起见，将第一个字符设定为相同
        str=' '+str;
        pattern=' '+pattern;
        dp[0][0]=true;

        for(int i=0;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                //遇到单独的* ，需要根据* 前面的一个字母进行判断
                if(j+1<=m&&pattern[j+1]=='*')
                {
                    continue;;
                }

                if(i!=0&&pattern[j]!='*')
                {
                    //单个字母匹配的情况
                    //取决于上个状态匹配 并且 当前字母匹配（包含字母相等或. 的情况）
                    dp[i][j]=dp[i-1][j-1]&&(str[i]==pattern[j]||pattern[j]=='.');
                }
                else if(pattern[j]=='*')    //不能为else，否则i=0的情况没有涉及到
                {
                    //多个字母匹配的情况
                    //取决于p的前j-2都是匹配的(也可以表示*前面的字符一次都不出现)，或者s的前i-1与p的前j是匹配的(*前面的字符只出现一次)，并且s的当前的和p的j-1也是匹配的
                    dp[i][j]=dp[i][j-2] || i>0&& (dp[i-1][j]&&(str[i]==pattern[j-1]||pattern[j-1]=='.')); 
                }
            }
        }

        return dp[n][m];

    }
};

时间复杂度分析： 表示 s 的长度， 表示 p 的长度，总共 个状态，状态转移复杂度 ，所以总时间复杂度是