Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for the following special characters:
.matches any single character.*matches zero or more of the preceding element.
The matching should cover the entire input string s, not just a substring. Return true if s matches p; otherwise, return false.
Example 1
Input
s = "aa", p = "a"Output
falseThe pattern
a matches exactly one a, but s contains two characters.Example 2
Input
s = "aa", p = "a*"Output
trueThe
* means zero or more of the preceding a, so a* can match aa.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 that for each appearance of '*', there will be a previous valid character to match.