Match a string with wildcard pattern recursively

Implement a function that checks whether an input string matches a wildcard pattern.

Pattern rules

• ? matches exactly one character.
• * matches any sequence of characters, including the empty sequence.
• All other characters match themselves.

Input

• A string s
• A pattern string p

Output

• Return true if s matches p entirely (not a substring match), otherwise false .

Examples

• s = "aa" , p = "a" → false
• s = "aa" , p = "*" → true
• s = "cb" , p = "?a" → false
• s = "adceb" , p = "*a*b" → true

Constraints (typical interview assumptions)

• 0 ≤ len(s), len(p) ≤ 2000
• You should discuss a recursive approach and how to avoid exponential blow-up.