258. Wildcard Matching

Given an input string s and a pattern p, return true if p matches the entire string. '?' matches any single character; '*' matches any sequence of characters (including empty). Input: '"s", "p"'.

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

Output: Boolean — true or false.

Examples

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

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

Input: "adceb", "*a*b"
Output: true
Explanation: Stars absorb other chars.

Constraints

• 0<=s.length,p.length<=2000
• p contains lowercase, '?', '*'

Asked by