Problem Statement
Regular Expression Matching
You get a plain string s, like "aab", and a pattern p, like "c*a*b". You have to decide if the pattern describes the whole string. The pattern uses two special characters. A dot '.' is a wildcard that matches any one single character. A star '*' means "zero or more of the thing right before it". So "a*" means zero or more a's, and ".*" means zero or more of anything. The answer is true if the pattern matches the entire string, and false if it does not.
Signals to notice
Brute force first
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.
The key insight
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.
Trace it on s="aab", p="c*a*b"
init: dp[0][0]=true, all else false (m=3, n=5) empty-s row: j=2 'c*' -> dp[0][2]=dp[0][0]=true; j=4 'a*' -> dp[0][4]=dp[0][2]=true i=1 (s='a'): 'c*' j=2 -> dp[1][2]=dp[1][0]=false; 'a*' j=4 -> dp[1][4]=dp[1][2]=false, then a==a so |= dp[0][4]=true i=2 (s='a'): 'a*' j=4 -> dp[2][4]=dp[2][2]=false, then a==a so |= dp[1][4]=true i=3 (s='b'): 'a*' j=4 -> dp[3][4]=dp[3][2]=false, b!=a so stays false i=3, j=5 'b': p[4]=='b'==s[2]=='b' -> dp[3][5]=dp[2][4]=true return dp[3][5] = true
What must stay true
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.
Shape of the loop
dp[0][0] = true
for j: if p[j]=='*': dp[0][j] = dp[0][j-2] # '*' can erase preceding char
for i, j:
if p[j]=='.' or p[j]==s[i]: dp[i][j] = dp[i-1][j-1] # consume matching char
elif p[j]=='*':
dp[i][j] = dp[i][j-2] # zero occurrences
if p[j-1]=='.' or p[j-1]==s[i]: dp[i][j] |= dp[i-1][j] # one more occurrence
return dp[m][n]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
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.