789. Wildcard Pattern Matching (? and *)

Given a string s and a pattern p containing '?' (matches any single char) and '*' (matches any sequence of chars including empty), return true if p matches the entire string s, else false. Implement with recursion + memoization. Input: two quoted strings separated by comma.

Input: Two strings: "s", "p".

Output: Return a boolean: true or false.

Examples

Input: "aa", "*"
Output: true
Explanation: * matches any sequence.

Input: "cb", "?a"
Output: false
Explanation: ? matches c but a != b.

Input: "adceb", "*a*b"
Output: true
Explanation: * matches '', a matches a, * matches 'dce', b matches b.

Constraints

• 0 <= s.length <= 20
• 0 <= p.length <= 20
• p contains a-z, ?, *

Asked by