题目

给定两个字符串, 第一个字符串是英文字符a-z,第二个字符串是正则表达式.
正则表达式只有a-z, '*', '.'.
.表示任何字符.
*表示0或多个字符.

Input: s = "mississippi", p = "mis*is*p*."
Output: false

Input: s = "aab", p = "c*a*b"
Output: true

Input: s = "ab", p = ".*"
Output: true

Input:s = "aa", p = "a*"
Output: true

思路1

递归. 效率太低.
先查看第一个字符是否相等. 然后看后面字符, 如果后面字符有就移动p, 如果没有就同时移动s和p.

bool isMatch(string s, string p) {
    if (p.empty()) {
        return s.empty();
    }

    bool isFirstMatch = !s.empty() && (p[0] == s[0] || p[0] == '.');

    if (p.size() > 1 && p[1] == '*') {
        return isMatch(s, p.substr(2)) || (isFirstMatch && isMatch(s.substr(1), p));
    } else {
        return isFirstMatch && isMatch(s.substr(1), p.substr(1));
    }
}

思路2

动态规划. 自底向上规划. 效率高, 太难理解.

bool isMatch(string s, string p) {
    int m = (int)p.size();
    int n = (int)s.size();

    vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
    // s,p都为空时为true
    f[0][0] = true;

    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            int ii = i - 1;
            int jj = j - 1;
            if (p[ii] == '*' && i > 1) {
                f[i][j] = f[ii-1][j];
                if (jj >= 0 && (p[ii-1] == s[jj] || p[ii-1] == '.')) {
                    f[i][j] = f[i][j] || f[i][jj];
                }
            } else {
                f[i][j] = jj >= 0 && (p[ii] == s[jj] || p[ii] == '.') && f[ii][jj];
            }
        }
    }

    return f[m][n];
}