dp[i][j] = true if s[0..i] matches p[0..j]. handle three cases: exact match, . matches any, * matches zero or more of preceding character.
for *, try both zero matches (skip pattern) and one or more matches (consume string if character matches). use memoization to avoid recomputation.
cases
- exact match: s[i] == p[j]
- dot: p[j] == '.' matches any character
- star: p[j] == '*' matches zero or more of p[j-1]
complexity
O(mn) time where m and n are string and pattern lengths. O(mn) space for dp table.