State

dp[i][j] = does s[0..i-1] match p[0..j-1]?

Advertisement

Transition

if (p[j-1] == '.' || p[j-1] == s[i-1])
  dp[i][j] = dp[i-1][j-1];
else if (p[j-1] == '*') {
  dp[i][j] = dp[i][j-2];  // zero of preceding
  if (p[j-2] == '.' || p[j-2] == s[i-1])
    dp[i][j] |= dp[i-1][j];  // one or more
}
Advertisement

Base cases

dp[0][0] = true. dp[0][j] = true if p starts with 'x*y*...' (zero-matches only).

Trickiest part

The * character. It refers to the PRECEDING char/dot. Look back at p[j-2].