正则表达式匹配

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

思路：

记dpi表示s[0...i]和p[0...j]能否完全匹配，true表示能匹配，false表示不能匹配。如果s[i]==p[j]，或者p[j]=='.'。则dp[i][j]=dp[i-1][j-1]。如果p[j]=='*'，如果p[j-1]和s[i]相等，则dp[i][j]=dp[i-1][j]或者dp[i][j]=dp[i][j-2]。如果p[j-1]和s[i]不相等，则dp[i][j]=dp[i][j-2]。合起来就是dp[i][j]=dp[i][j-2]，如果p[j-1]和s[i]相等或者p[j-1]=='.'，则dp[i][j] = dp[i-1][j]

代码:

class Solution {
public:
    bool isMatch(string s, string p) {
        int sl = s.length();
        int pl = p.length();
        //i和j比实际下标大1
        auto match = [&](int i, int j) {
            if(i == 0) {
                return false;
            }
            if(p[j-1] == '.') {
                return true;
            }
            return s[i-1] == p[j-1];
        };
        //长度加1，答案就是dp[sl][pl]
        vector<vector<bool>> dp(sl+1,vector<bool>(pl+1));
        //s和p都是长度为0的字符串，此时s和p是匹配的。
        dp[0][0] = true;
        for(int i = 0;i <= sl;i++) {
            for(int j = 1;j <= pl;j++) {
                if(p[j-1] == '*') {
                    //如果p的当前字符为'*'，则有如下结果
                    dp[i][j] = dp[i][j] || dp[i][j-2];
                    if(match(i,j-1)) {
                        //如果s当前的字符和p当前的上一个字符相等，则，有如下结果
                        dp[i][j] = dp[i][j] || dp[i-1][j];
                    } 
                }
                else {
                    if(match(i,j)) {
                        dp[i][j] = dp[i][j] || dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[sl][pl];
    }
};