1170. Wildcard Matching (? and *)

Given a string s and a pattern p containing lowercase letters, '?' (matches any single character), and '*' (matches any sequence including empty), determine whether p matches the entire string s. Return true or false. The input is JSON {s, p}.

Input: JSON {s, p}.

Output: Boolean — true or false.

Examples

Input: {"s":"aa","p":"*"}
Output: true
Explanation: '*' matches everything.

Input: {"s":"cb","p":"?a"}
Output: false
Explanation: 'a' does not match 'b'.

Input: {"s":"adceb","p":"*a*b"}
Output: true
Explanation: Stars absorb the gaps.

Constraints

• 0<=|s|,|p|<=2000

Asked by