Wildcard Matching

I had this on a Palantir backend onsite and the gotcha was the * recurrence. Most candidates write dp[i][j] = dp[i-1][j-1] || dp[i-1][j] (consume one char or zero), which works but misses the cleaner two-state recurrence: * either matches the empty string (dp[i][j-1]) or matches s[i] and stays available (dp[i-1][j]). The catalog covered regular-expression-matching (the more general . and *), but it skipped this two-token wildcard variant where the recurrence is genuinely simpler.

Wildcard Matching

Given an input string s and a pattern p, implement wildcard pattern matching with support for ? and * where:

• ? matches any single character.
• * matches any sequence of characters (including the empty sequence).

The matching should cover the ENTIRE input string (not partial).

Examples

Example 1:

• Input: s = "aa", p = "a"
• Output: false
• Explanation: "a" does not match the entire string "aa".

Example 2:

• Input: s = "aa", p = "*"
• Output: true
• Explanation: * matches any sequence.

Example 3:

• Input: s = "cb", p = "?a"
• Output: false
• Explanation: ? matches c, but the second character a does not match b.

Example 4:

• Input: s = "adceb", p = "*a*b"
• Output: true
• Explanation: First * matches the empty sequence; with the substring "a*b", * matches "dce".

Constraints

• 0 <= s.length, p.length <= 2000.
• s contains only lowercase English letters.
• p contains only lowercase English letters, ? or *.

Follow-up

The * recurrence has a 2-state form (empty match OR consume one char and keep * available); it's also possible to write it as a 3-state form (empty / one / many). Why does the 2-state form suffice? Because "many" decomposes into "one consumed plus the * still available", which is exactly the second branch. By induction the * either matches no chars at all or absorbs one and recurses with the SAME pattern position, so two transitions cover every case.