259. Regular Expression Matching

Given an input string s and a pattern p, return true if p matches the entire string. '.' matches any single character; '*' matches zero or more of the preceding element. Input: '"s", "p"'.

Input: '"s", "p"'.

Output: Boolean — true or false.

Examples

Input: "aa", "a"
Output: false
Explanation: 'a' does not cover 'aa'.

Input: "aa", "a*"
Output: true
Explanation: 'a*' matches 'aa'.

Input: "aab", "c*a*b"
Output: true
Explanation: c* matches empty, a* matches aa.

Constraints

• 1<=s.length<=20
• 1<=p.length<=30
• valid pattern

Asked by