Hard
Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Examples: 1. Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa". 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". 3. Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Constraints
- 1 <= s.length <= 20 - 1 <= p.length <= 20 - s contains only lowercase English letters. - p contains only lowercase English letters, '.', and '*'. - It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
It is okay to have an O(n^2) time complexity. Use a 2D array to keep track of matching characters (read up on dynamic programming).
*hover to un-blur*
(This is a long one, you should of seen what the C++ solution looked like) class Solution { public: bool isMatch(string s, string p) { int n = s.length(), m = p.length(); bool dp[n+1][m+1]; memset(dp, false, sizeof(dp)); dp[0][0] = true; for(int i=0; i<=n; i++){ for(int j=1; j<=m; j++){ if(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[n][m]; } };