10.正则表达式匹配

1.字符串为传递参数的递归法
2.指针为传递参数的递归法
3.记忆化递归法
4.动态规划

3.记忆化递归代码

class Solution {
public:
    vector<vector<int> > memo;
    char *str, *ptr;
    int slen, plen;
    bool isMatch(string s, string p) {
        slen = s.size();
        plen = p.size();
        str = &s[0];
        ptr = &p[0];
        memo.resize(slen + 1);
        for (int k = 0; k <= slen; ++k)
        {
            memo[k].resize(plen + 1, 3);
        }
        reverse(s.begin(), s.end());
        reverse(p.begin(), p.end());
        return Match(0, 0);
    }
    bool Match(int i, int j) {
        if(i == slen && j == plen) {
            memo[i][j] = 1;
            return true;
        }
        if (i == slen && j != plen) {
            if (*(ptr + j) != '*') {
                memo[i][j] = 0;
                return false;
            }
            if (*(ptr + j) == '*') {
                if (memo[i][j + 2] == 3) memo[i][j + 2] = (Match(i, j + 2) ? 1 : 0);
                return memo[i][j + 2];
            }
        }
        if(i != slen&& j == plen) {
            memo[i][j] = 0;
            return false;
        }
        if (*(str + i) == *(ptr + j) || *(ptr + j) == '.') {
            if (memo[i + 1][j + 1] == 3) memo[i + 1][j + 1] = Match(i + 1, j + 1) ? 1 : 0;
                return memo[i + 1][j + 1];
        }
        if (*(ptr + j) == '*') {
            if (*(ptr + j + 1) == *(str + i) || *(ptr + j + 1) == '.') {
                if (memo[i + 1][j] == 3) memo[i + 1][j] = (Match(i + 1, j) ? 1 : 0);
                if (memo[i][j + 2] == 3) memo[i][j + 2] = (Match(i, j + 2) ? 1 : 0);
                return memo[i + 1][j] || memo[i][j + 2];
            }
            if (*(ptr + j + 1) != *(str + i)) {
                if (memo[i][j + 2] == 3) memo[i][j + 2] = (Match(i, j + 2) ? 1 : 0);
                return memo[i][j + 2];
            }
        }
        return false;
    }
};