Regular Expression Matching

Hard

Given a string s (first line) and a pattern p (second line) supporting . (any single char) and * (zero or more of the preceding element), return true if the pattern matches the entire string.

Example 1

Input:  s = "aa", p = "a*"
Output: true

Example 2

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

Example 3

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

Constraints

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• Each * has a valid preceding element.