剑指 Offer 19. 正则表达式匹配https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

动态规划：通过dp数组剪枝

只需要对各种情况进行分类处理即可

vector<vector<int>> dp;bool helper(const string& s, const int i, const string& p, const int j)
{// base caseif (j == p.size()){return i == s.size();}if (i == s.size()){if ((p.size() - j) % 2 == 1){return false;}for (int k = j + 1; k < p.size(); k += 2){if (p[k] != '*'){return false;}}return true;}if (dp[i][j] != -1){return dp[i][j];}bool res = false;if (s[i] == p[j] || p[j] == '.'){if (j + 1 < p.size() && p[j + 1] == '*'){res = helper(s, i, p, j + 2) || helper(s, i + 1, p, j);}else{res = helper(s, i + 1, p, j + 1);}}else{if (j + 1 < p.size() && p[j + 1] == '*'){res = helper(s, i, p, j + 2);}}dp[i][j] = res;return res;
}bool isMatch(string s, string p) {int i = s.size(), j = p.size();dp.resize(i, vector<int>(j, -1));return helper(s, 0, p, 0);
}