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

1. 懂了动态规划的路径。
2. 注意dp[0][0] = true不要覆盖。
3. 遇到号时，记得或运算，因为可以不管那个号。
4. 其实边界条件就是让dp或者数组不超就行，因为开始条件已经初始化好的呢。并会自动具有各自的意义（数组的意义和动态规划方程的意义）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here

        vector<vector<bool>> dp(str.size()+1, vector<bool>(pattern.size()+1, false));

        //空串和空正则
        dp[0][0] = true;

        //非空子串和空正则全为false
        //空字串和非空正则需要进行计算。

        for(int i =0; i<=str.size();i++ ){
            for(int j= 0; j<=pattern.size();j++ ){
                if(j==0){//空正则
                    dp[i][j] = i==0;//别把dp[0][0] = true 给覆盖了
                    continue;
                }else{
                    if(pattern[j-1]!='*'){
                        if(i>0&&(str[i-1]==pattern[j-1]||pattern[j-1]=='.')){//考虑边界条件
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }else{

                        if(j>=2){//边界条件
                            dp[i][j] =  dp[i][j] || dp[i][j-2];//遇到*可以选择忽略他，所以有个或
                        }

                        if(i>=1&&j>=2&&(str[i-1]==pattern[j-2]||pattern[j-2]=='.')){
                            dp[i][j] = dp[i][j] || dp[i-1][j];//遇到*可以选择忽略他，所以有个或
                        }

                    }
                }


            }
        }

        return dp[str.size()][pattern.size()];



    }
};