Hints — p72 Regular Expression Matching

Hint 1. Define dp[i][j] = True iff s[:i] matches p[:j]. The empty-prefix base case dp[0][0] = True. Empty string can match patterns like a*b*c* — initialize dp[0][j] carefully.

Hint 2. Three cases for the last pattern char p[j-1]:

• Regular char or .: dp[i][j] = dp[i-1][j-1] AND matches(s[i-1], p[j-1]).
• *: forms a pair with p[j-2]. Two sub-cases — see hints 3 and 4.

Hint 3. * case A — match ZERO of preceding: dp[i][j] = dp[i][j-2] (skip the (char, *) pair entirely).

Hint 4. * case B — match ONE MORE of preceding: if s[i-1] matches p[j-2], then dp[i][j] = dp[i][j] OR dp[i-1][j]. Note: dp[i-1][j] (not dp[i-1][j-2]) — the * stays active to consume more chars.

Hint 5. Common bugs: forgetting the empty-prefix row; using j-1 instead of j-2 when pairing with *; treating * like LC 44 wildcard (which matches any sequence — different problem). Test s="", p="a*b*" → True.

If stuck: see solution.py.