Regular Expression Matching

You are given a string s and a pattern p. Implement a regular expression matcher that determines whether p describes the entirety of s.

The pattern supports these two special constructs:

• A period ('.') matches any single character.
• An asterisk ('*') means zero or more copies of the character that appears immediately before it.

The matching must cover the whole input string — partial matches should be rejected. Return true if the pattern consumes all of s, otherwise false.

Example 1:

Input: s = "ab", p = ".*"

Output: true

Explanation: ".*" means "zero or more of any character", which can match "ab" completely.

s = ab
p = .*

true

Example 2:

Input: s = "mississippi", p = "mis*is*ip*."

Output: false

Example 3:

Input: s = "", p = "c*d*"

Output: true

Constraints:

• 0 <= s.length <= 20
• 1 <= p.length <= 30
• s contains only lowercase English letters ('a' to 'z').
• p contains only lowercase English letters, '.', and '*'.
• Every '*' in p is always preceded by a valid character (no isolated or consecutive '*' tokens).
• The whole string s must be matched; partial matching is not sufficient.

Example (as reported)

Input:
aa
a

Output:
false