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). Return true or false.
Examples
Input:
s = "aa", p = "a"Output:
falseExplanation:
Pattern a has length 1 but string aa has length 2. No wildcards to extend the match.
Input:
s = "aa", p = "a*"Output:
trueExplanation:
A* means zero or more as. It matches aa by using a twice. DP validates match.
Input:
s = "ab", p = ".*"Output:
trueExplanation:
.* = zero or more of any char. Matches ab by consuming both chars with .-star.
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.