35. Regular Expression Matching

Hard · String

Given an input string `s` and a pattern `p`, implement regular expression matching with support for `.` and `*`. The `.` character matches any single character, while `*` matches zero or more of the preceding element. The matching should cover the **entire** input string (not partial).

The pattern rules are: `.` matches any single character; `*` matches zero or more of the preceding element. You may assume `s` contains only lowercase letters, and `p` contains only lowercase letters, `.`, and `*`.

Return `true` if the pattern matches the entire string, or `false` otherwise.

Examples

Example 1
Input: s = "aa", p = "a*"
Output: true
Explanation: 'a*' means zero or more 'a' characters. Since the string is "aa", two 'a's are matched.
Example 2
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: 'c*' matches zero 'c's, 'a*' matches two 'a's, and 'b' matches 'b'. The entire string is covered.

Constraints