dsa · hard

Wildcard Matching

Return whether the whole of s matches pattern p.

Arguments

• s — the text that must match in full
• p — wildcard pattern; "?" is one char, "*" is any sequence

p may contain ordinary lowercase letters plus two specials: "?" matches any one character, and "*" matches any sequence of characters (including the empty sequence). A "*" does not need a character in front of it.

Matching is of the entire string, not a substring.

Example

s = "aa", p = "a" → false (p is only one character).

s = "aa", p = "*" → true (the star eats both letters).

s = "cb", p = "?a" → false (? can be c, but then a ≠ b).

s = "adceb", p = "*a*b" → true (* + a + * + b).

Constraints

0 <= s.length, p.length <= 2000 s contains only lowercase letters p contains lowercase letters, "?" and "*" Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
"aa"
"a"

Expected:
false

Example 2

Input:
"aa"
"*"

Expected:
true

Example 3

Input:
"cb"
"?a"

Expected:
false

Open in the Dojo editor