Description
Given an input string s and a pattern p, implement regular expression matching with support for '.' (matches any single character) and '*' (matches zero or more of the preceding element).
Examples
Input:
s = "aa", p = "a"Output:
falseExplanation:
"a" does not match the entire string "aa".
Input:
s = "aa", p = "a*"Output:
trueExplanation:
"*" means zero or more of the preceding element, "a".
Input:
s = "ab", p = ".*"Output:
trueExplanation:
".*" 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 '*', there is a preceding valid character to match.