Implement pattern matching with two special characters: . matches any single character, and * matches zero or more copies of the element right before it.
The match must cover the entire string s, not just part of it. Return true if s matches the pattern p.
Examples
Example 1
- Input
- s = "aa", p = "a"
- Output
- false
- Why
- "a" matches only one character, not the whole string.
Example 2
- Input
- s = "aa", p = "a*"
- Output
- true
Example 3
- Input
- s = "ab", p = ".*"
- Output
- true
- Why
- ".*" matches any sequence of characters.
Constraints
1 <= s.length, p.length <= 20scontains only lowercase letters;pcontains lowercase letters,.and*.- Every
*has a letter or.right before it.