Wildcard Matching
hardTime: O(m*n)Space: O(m*n)
Recognize the pattern
wildcard pattern matching? = one char, * = any sequence2D DP
Brute force idea
Recursive without memo — exponential.
Better approach
dp[i][j] = s[0..i-1] matches p[0..j-1]. For *: dp[i][j] = dp[i][j-1] || dp[i-1][j]. For ?: dp[i-1][j-1]. O(mn).
Key invariant
* has two choices: match empty (dp[i][j-1]) or match one more char (dp[i-1][j]). ? matches any single char.
Watch out for
Confusing * here vs regex * — wildcard * matches any sequence independently.