dp[i][j] = true if s[0..i] matches p[0..j]. ? matches any single character. * matches any sequence including empty.
for *, try matching zero characters (skip *) or one or more characters (consume string). can optimize space to O(n) by using only previous row.
cases
- exact match: s[i] == p[j]
- ?: p[j] == '?' matches any character
- *: matches zero or more characters
complexity
O(mn) time where m and n are string and pattern lengths. O(mn) space, can be optimized to O(n).