44. Wildcard Matching
You receive a text string s (lowercase letters, possibly empty) and a pattern p built from lowercase letters plus two wildcards:
?matches exactly one arbitrary character,*matches any run of characters, including the empty run.
A plain letter in the pattern matches only itself. Return true if the pattern accounts for the whole string from first character to last — partial coverage does not count — and false otherwise.
Note how * here differs from regex: it is a standalone 'match anything' token, not a repeat of the previous character.
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: The pattern consumes one 'a' and then has nothing left for the second one.
Example 2:
Input: s = "aa", p = "*"
Output: true
Explanation: A lone star swallows the entire string.
Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' happily takes 'c', but 'a' cannot match 'b'.
Example 4:
Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first star matches the empty run, 'a' matches 'a', the second star matches "dce", and 'b' matches 'b'.
Constraints:
- 0 ≤ s.length, p.length ≤ 2000
- s contains only lowercase English letters
- p contains only lowercase English letters, '?', and '*'
Hints:
Define match(i, j) = 'does p[j:] cover s[i:]?'. Letters and '?' consume one character from each side; '*' branches into two choices: match nothing (advance j) or eat one character and stay (advance i).
That recursion memoizes into an (n+1) × (m+1) boolean table filled row by row — the standard O(n·m) DP. Mind the first row: dp[0][j] is true only while p's prefix is all stars.
For near-O(1) space, walk both strings greedily and remember the position of the most recent '*' plus how much it has eaten. On a dead end, reopen that star one character wider and retry from there — only the last star ever needs revisiting.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "aa", p = "a"
Expected output: false