Wildcard Matching
hardTime: O(m*n)Space: O(m*n)
Signals to notice
wildcard pattern matching? = one char, * = any sequence2D DP
Brute force first
Recursive without memo — exponential.
The key insight
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).
What must stay true
* has two choices: match empty (dp[i][j-1]) or match one more char (dp[i-1][j]). ? matches any single char.
Easy way to go wrong
Confusing * here vs regex * — wildcard * matches any sequence independently.