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

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        // 动态规划
        int strlen=str.length();
        int patternlen=pattern.length();
        bool dp[strlen+1][patternlen+1];
        
        // 初始化动态规划的二维数组前两个
        dp[0][0]=true;
        dp[0][1]=false;
        
        // 初始化第一行
        for(int i=2;i<=patternlen;i++)
            if(pattern[i-1]=='*')
                dp[0][i]=dp[0][i-2];
            else
                dp[0][i]=false;
        
        // 初始化第一列 都是false
        for(int j=1;j<strlen;j++)
            dp[j][0]=false;
        
        
        // 开始动态规划
        for(int i=1;i<=strlen;++i)
        {
            for(int j=1;j<=patternlen;++j)
            {
                // 如果当前字符串是匹配的（包括.） 则二维数组的值 等于左上角的值
                if(str[i-1] == pattern[j-1] || pattern[j-1]=='.')
                    dp[i][j]=dp[i-1][j-1];
                // 如果说当前的字符是*
                else if (pattern[j-1] == '*')
                {
                    // 遇到* 先假设判断*前面的字符出现0次，直接跳过判断*前字符是否相等
                    // 直接让结果等于*前两个的字符
                    // 比如说：aa[a]     aab[*]a
                    // 此时看到*了，直接忽视b 看前面a的数组是否匹配着+
                    // aa[b]bba     aab[*]a 直接匹配前面的aa 匹配 直接返回true
                    dp[i][j]=dp[i][j-2];

                    // 如果上面匹配，下面的判断是或 直接就是true了，也不用判断*前面的字符是什么 是否还需要匹配 
                    // 如果上面的字符再往前不匹配了
                    // aab[b]ba     aab[*]a 在匹配括号的阶段的时候，上面的判断只是匹配了aab和aa 是false
                    // 就要到下面判断 *前面的字符是否匹配
                    // aabb[b]a     aab[*]a 就要向上一个行的位置看aabb是否匹配 
                    // 上一行个位置代表 前面如果重复了*前面的字符，结果是否正确
                    // "aabba","aab*a"  看输出的结果会在倒数第二列 出现一列1
                    if(pattern[j-2]=='.' || pattern[j-2]==str[i-1])
                        dp[i][j]= dp[i][j] || dp[i-1][j];
                }
                else
                    dp[i][j]=false;
            }
        }
        
//         for(int i=0;i<=strlen;i++)
//         {
//             for(int j=0;j<=patternlen;j++)
//                 cout<<dp[i][j]<<" ";
//             cout<<endl;
//         }
        return dp[strlen][patternlen];
    }
};