LeetCode 44 Wildcard Matching - State Design

Define $dp[i][j]$ = true if $s[0..i-1]$ matches $p[0..j-1]$.

Base cases: $dp[0][0] = true$ (empty matches empty), $dp[0][j] = true$ if $p[0..j-1]$ is all '*' (stars can match empty), and $dp[i][0] = false$ for $i > 0$ (non-empty string can't match empty pattern).

The '*' transition is the tricky part: it can match zero characters ($dp[i][j-1]$) or one-or-more characters ($dp[i-1][j]$).