LeetCode 44 Wildcard Matching - Walkthrough

Match pattern $p$ with wildcards against string $s$. '?' matches any char, '*' matches any sequence. $dp[i][j]$ = true if $p[0..i-1]$ matches $s[0..j-1]$.

Handle '' carefully: it can match empty or extend. For '': $dp[i][j] = dp[i-1][j]$ (match empty) OR $dp[i][j-1]$ (extend match). For '?': $dp[i][j] = dp[i-1][j-1]$. Example: pattern "a*b" matches "axxxb", "ab", "axyzzb". Time: $O(mn)$, Space: $O(mn)$ or $O(n)$ with improvement.