jjc
10. Regular Expression Matching(hard)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: falseExplanation: "a" does not match the entire string "aa".Example 2:Input:s = "aa"p = "a*"Output: trueExplanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".Example 3:Input:s = "ab"p = ".*"Output: trueExplanation: ".*" means "zero or more (*) of any character (.)".Example 4:Input:s = "aab"p = "c*a*b"Output: trueExplanation: 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: falseAccepted 298,051 Submissions 1,182,171
class Solution_S4ms {public: bool isMatch(string s, string p) { bool **dp = new bool*[s.length() + 1](); for(int i = 0; i < s.length() + 1; ++i) { dp[i] = new bool[p.length()+1]; memset(dp[i], 0, p.length()+1); } dp[s.size()][p.size()] = true; for (int i = s.length(); i >= 0; i--){ for (int j = p.length() - 1; j >= 0; j--) { bool first_match = (i < s.length() && (p[j] == s[i] || p[j] == '.')); if (j + 1 < p.length() && p[j+1] == '*') { dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j]; } else { dp[i][j] = first_match && dp[i+1][j+1]; } } } return dp[0][0]; }};class Solution_S8ms {public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector > dp(m + 1, vector (n + 1, false)); dp[0][0] = true; for (int i = 0; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (j > 1 && p[j - 1] == '*') { dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]); } else { dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'); } } } return dp[m][n]; }};
/* https://www.cnblogs.com/grandyang/p/4461713.html * dp[i][j]表示s[0,i)和p[0,j)是否match1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.*/class Solution_grandyang {public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector > dp(m + 1, vector (n + 1, false)); dp[0][0] = true; for (int i = 0; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (j > 1 && p[j - 1] == '*') { dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]); } else { dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'); } } } return dp[m][n]; }};