Regular Expression Matching — Step-by-Step Visualization

Algorithm Pattern

2-D DP (bottom-up)

Key Idea

dp[i][j] = does s[i:] match p[j:]? Fill from bottom-right; base case dp[m][n] = True.

Step-by-Step Approach

1. Create (m+1)×(n+1) table, all False. Set dp[m][n] = True.
2. Iterate i from m→0, j from n-1→0.
3. match = i<m and (s[i]==p[j] or p[j]=='.').
4. If p[j+1]=='*': dp[i][j] = dp[i][j+2] (skip *) OR (match and dp[i+1][j]) (use *).
5. Else if match: dp[i][j] = dp[i+1][j+1].
6. Answer is dp[0][0].

Common Gotchas

• '*' cannot appear first — always look at p[j+1] to decide if current char has a star.
• dp[i][j+2] handles 'zero occurrences' of the starred char.
• Fill bottom-up so dp[i+1][j] and dp[i][j+2] are already computed.