All problems

Wildcard Matching

Hard · dynamic programming

You are given a text s and a pattern p. The pattern is made of three kinds of symbol:

• a lowercase letter, which matches that same letter;
• ?, which matches exactly one character, any character;
• *, which matches any run of characters, including an empty run.

Return true if the pattern matches the whole of s from the first character to the last, and false otherwise. Matching only a piece of s does not count.

Either string may be empty. An empty pattern matches only an empty text.

Examples

Example 1

Input: s = "cabbage", p = "c*b?ge"

Output: true

Read it as c, then * standing for "ab", then b, then ? standing for "a", then g and e.

Example 2

Input: s = "abc", p = "a?"

Output: false

The pattern stops after two characters, but the text has three.

Example 3

Input: s = "", p = "***"

Output: true

Each star can stand for an empty run, so the pattern matches the empty text.

Constraints

• 0 <= len(s) <= 2000
• 0 <= len(p) <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, ? and *.