/*
* @lc app=leetcode id=10 lang=cpp
*
* [10] Regular Expression Matching
*
* https://leetcode.com/problems/regular-expression-matching/description/
*
* algorithms
* Hard (25.60%)
* Likes: 2994
* Dislikes: 564
* Total Accepted: 336.7K
* Total Submissions: 1.3M
* Testcase Example: '"aa"\n"a"'
*
* Given an input string (s) and a pattern (p), implement regular expression
* matching with support for '.' and '*'.
*
*
* '.' Matches any single character.
* '*' Matches zero or more of the preceding element.
*
*
* The matching should cover the entire input string (not partial).
*
* Note:
*
*
* s could be empty and contains only lowercase letters a-z.
* p could be empty and contains only lowercase letters a-z, and characters
* like . or *.
*
*
* Example 1:
*
*
* Input:
* s = "aa"
* p = "a"
* Output: false
* Explanation: "a" does not match the entire string "aa".
*
*
* Example 2:
*
*
* Input:
* s = "aa"
* p = "a*"
* Output: true
* Explanation: '*' means zero or more of the preceding element, 'a'.
* Therefore, by repeating 'a' once, it becomes "aa".
*
*
* Example 3:
*
*
* Input:
* s = "ab"
* p = ".*"
* Output: true
* Explanation: ".*" means "zero or more (*) of any character (.)".
*
*
* Example 4:
*
*
* Input:
* s = "aab"
* p = "c*a*b"
* Output: true
* Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore,
* it matches "aab".
*
*
* Example 5:
*
*
* Input:
* s = "mississippi"
* p = "mis*is*p*."
* Output: false
*
*
*/
class Solution {
public:
bool isMatch(string s, string p) {
const int M = s.size(), N = p.size();
vector<vector<bool>> dp(M + 1, vector<bool>(N + 1));
dp[0][0] = true;
for (int j = 2; j <= N; ++j) {
if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
}
for (int i = 1; i <= M; ++i) {
for (int j = 1; j <= N; ++j) {
const char a = s[i - 1], b = p[j - 1];
if (b == '*') {
dp[i][j] = dp[i][j - 2];
if (!dp[i][j] && (p[j - 2] == '.' || p[j - 2] == a)) dp[i][j] = dp[i - 1][j];
} else if (dp[i - 1][j - 1] && (b == '.' || a == b)) {
dp[i][j] = true;
}
}
}
return dp[M][N];
}
};