Wildcard Matching

Hard

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

Example 1

Input:  s = "aa", p = "a"
Output: false

Example 2

Input:  s = "aa", p = "*"
Output: true

Example 3

Input:  s = "cb", p = "?a"
Output: false

Constraints

• 0 <= s.length, p.length <= 16
• s contains only lowercase letters.
• p contains lowercase letters, '?' and '*'.