Regular Expression Matching
Recognize the pattern
Brute force idea
The naive version of Regular Expression Matching sounds like this: Try all possible matches recursively without memoization — exponential due to * branching into zero or more matches. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
Better approach
A calmer way to see Regular Expression Matching is this: 2D DP: dp[i][j] = does s[0.i-1] match p[0.j-1]? For * at p[j-1]: either use zero occurrences (dp[i][j-2]) or match one more (dp[i-1][j] if s[i-1] matches p[j-2]). The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Key invariant
The truth you want to protect throughout Regular Expression Matching is this: The * operator has two choices: zero occurrences of the preceding character (skip both pattern chars) or one more occurrence (consume one string char, keep the pattern position). This binary choice at each step creates the DP structure. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Watch out for
The trap in Regular Expression Matching usually looks like this: Treating * as matching the current character — it matches the PRECEDING character zero or more times. The * never appears alone; it's always attached to the character before it. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.