10. Regular Expression Matching
Implement regular-expression matching (LeetCode #10) supporting two special symbols. You receive a string s made of lowercase letters (possibly empty) and a pattern p made of lowercase letters plus the wildcards . and *.
.matches any single character.*matches zero or more copies of the element that immediately precedes it.
A * never appears first and always has a valid preceding element, so tokens come in pairs like a* or .*. The match must cover the entire string s, not just a prefix.
Return true if the whole of s can be produced by the pattern, and false otherwise (printed in lowercase).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" only matches a single character, so it cannot cover the two-letter string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: "a*" means zero or more 'a'. Taking two copies of 'a' matches all of "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means zero or more of any character, which can match the whole string "ab".
Constraints:
- 0 ≤ s.length ≤ 20
- 1 ≤ p.length ≤ 20
- s contains only lowercase English letters.
- p contains only lowercase English letters plus '.' and '*'.
- Every '*' in p has a valid preceding element (no leading '*').
Hints:
Think about matching one pattern token at a time. A letter or '.' consumes exactly one character of s, the tricky token is 'X*'.
When you see 'X*', you have two choices: use zero copies (skip the whole 'X*' group) or, if 'X' matches the current character, consume that character and stay on 'X*'.
Cache results by (index in s, index in p). Both a top-down memoized recursion and a bottom-up dp[i][j] table capture exactly those states in O(m*n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "aa", p = "a"
Expected output: false