Wildcard Matching

Problem Match string s against pattern p containing '?' (any single character) and '*' (any sequence, including empty). The match must cover the ENTIRE string. Expect a variant twist — pin exact semantics first.

Input / Output

• Input: strings s, p. Output: boolean full match.

Constraints

• Lengths up to 2000; O(mn) DP accepted; the greedy two-pointer runs O(m+n) average.

Example

• s="adceb", p="ab" → true; s="acdcb", p="ac?b" → false; s="aa", p="" → true.

Expected approach

• DP: dp[i][j] = s[0..i) matches p[0..j); '' → dp[i][j−1] (empty) OR dp[i−1][j] (extend); '?'/char → dp[i−1][j−1] on match; dp[0][j] true only for leading ''s. O(mn).
• Greedy alternative: walk two pointers, remember the last '*' position and the s-index it matched to; on mismatch, backtrack to star and let it swallow one more char. O(mn) worst, near-linear typical.
• Contrast with Regular Expression Matching (LC10) where '*' binds to the PRECEDING element — the classic confusion probe.