44. Wildcard Matching - Detailed Explanation

Problem Statement

Given an input string s and a pattern p, implement wildcard pattern matching with support for two special characters:

• ? matches exactly one arbitrary character.
• * matches any sequence of characters (including the empty sequence).

Determine if the entire string s matches the pattern p.

Examples

s = "aa", p = "a"            → false
s = "aa", p = "*"            → true
s = "cb", p = "?a"           → false
s = "adceb", p = "*a*b"      → true   ( '*' matches "adce" )
s = "acdcb", p = "a*c?b"      → false

Constraints

• 0 ≤ s.length, p.length ≤ 2000
• s and p consist of only lowercase letters plus the characters ? and *.

Hints

1. A naïve backtracking solution may re‑explore the same subproblems many times—use memoization.
2. You can view this as a 2D DP: whether s up to index i matches p up to index j.
3. Long runs of * can be collapsed (e.g. treat "**" the same as "*").

Approach 1 Backtracking with Memoization

Define a function match(i, j) that returns whether s[i:] matches p[j:].

1. Base cases
   • If j == p.length, return i == s.length.
   • If i == s.length, the remainder of p[j:] must be all * to match.
2. Recurrence
   • If p[j] is a letter or ?, they match if i < s.length and (p[j] == s[i] or p[j] == '?'), and then match(i+1, j+1).
   • If p[j] == '*', two choices:
     • Treat * as matching zero characters → match(i, j+1).
     • Treat * as matching one character → if i < s.length, match(i+1, j).
3. Memoize every (i,j) to avoid exponential blow‑up.

Time Complexity: O(m × n) states, each computed in O(1) amortized → O(m × n)
Space Complexity: O(m × n) for recursion stack + memo table

Approach 2 Dynamic Programming 2D

Define a boolean table dp[i+1][j+1] meaning whether s[0…i) matches p[0…j).

1. Initialization
   • dp[0][0] = true (empty string matches empty pattern).
   • For j from 1…p.length:

     dp[0][j] = dp[0][j-1] AND (p[j-1] == '*')
     

     (an empty string can only match a sequence of *s).
2. Filling the table
   For i in 1…s.length, j in 1…p.length:
   • If p[j-1] is a letter or ?:

     dp[i][j] = dp[i-1][j-1] AND (p[j-1] == s[i-1] OR p[j-1] == '?')
     

   • If p[j-1] == '*':

     dp[i][j] = dp[i][j-1]    # '*' matches zero chars
             OR dp[i-1][j]    # '*' matches one more char
     

3. Answer
   Return dp[s.length][p.length].

Time Complexity: O(m × n)
Space Complexity: O(m × n) (can be optimized to O(n))

Space‑Optimized DP

Since each dp[i][*] row depends only on the previous row and the current row’s left cell, you can roll arrays and reduce space to O(n).

Python Code