243. Regular Expression Matching
🔗 LeetCode Problem: 10. Regular Expression Matching
📊 Difficulty: Hard
🏷️ Topics: Dynamic Programming, String, DP - Strings, Recursion
Problem Statement
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.'Matches any single character.'*'Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Constraints:
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s contains only lowercase English letters.
- p contains only lowercase English letters, '.', and '*'.
- It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
🧒 Let's Build Understanding from Absolute Scratch
What Does This Problem REALLY Ask?
Forget "regular expressions" for a moment. Let me understand what we're doing:
Given: s = "aa", p = "a"
Question: Does pattern match string?
Let me try:
s = "aa" (2 characters)
p = "a" (1 character)
'a' matches first 'a' in string ✓
But we have another 'a' in string!
Pattern is done, string is not!
Result: NO MATCH ✗
KEY INSIGHT: We need to match the ENTIRE string! 🔑
Example 2: s = "aa", p = "a*"
Question: What does '*' mean?
Let me think:
'*' means "zero or more of the PRECEDING element"
Preceding element is 'a'
So "a*" means: zero 'a's, one 'a', two 'a's, three 'a's, ...
Does "a*" match "aa"?
If we use TWO 'a's: "aa" ✓
Result: MATCH ✓
So '*' gives us CHOICES! This is the key! 🎯
Understanding the Special Characters
CHARACTER 1: '.' (dot)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
'.' matches ANY single character
Examples:
s = "a", p = "." → Match! ✓ ('.' matches 'a')
s = "b", p = "." → Match! ✓ ('.' matches 'b')
s = "5", p = "." → Match! ✓ ('.' matches '5')
s = "ab", p = "." → NO! ✗ ('.' matches only ONE char)
Think of '.' as a wildcard for EXACTLY ONE character!
CHARACTER 2: '*' (star)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
'*' matches ZERO OR MORE of the PRECEDING element
IMPORTANT: '*' doesn't work alone!
It modifies the character BEFORE it!
Examples:
"a*" means:
"" (zero 'a's) ✓
"a" (one 'a') ✓
"aa" (two 'a's) ✓
"aaa" (three 'a's) ✓
...
s = "aaa", p = "a*" → Match! ✓
s = "", p = "a*" → Match! ✓ (zero 'a's)
s = "b", p = "a*" → NO! ✗ (can only match 'a's)
".*" means:
"" (zero of any char) ✓
"a" (one char) ✓
"ab" (two chars) ✓
"xyz" (three chars) ✓
ANY string!
s = "anything", p = ".*" → Match! ✓
This is POWERFUL! 🔑
Why Is This Problem Hard?
The challenge: We have CHOICES!
Example: s = "aab", p = "a*b"
When we see "a*", we have MANY options:
Option 1: Use zero 'a's
Pattern becomes "b"
Try to match "aab" with "b" → Fail! ✗
Option 2: Use one 'a'
Pattern becomes "ab"
Try to match "aab" with "ab" → Fail! ✗
Option 3: Use two 'a's
Pattern becomes "aab"
Try to match "aab" with "aab" → Success! ✓
We don't know which choice is correct until we TRY them all!
Another example: s = "aaa", p = "a*a"
When we see "a*":
Option 1: Use zero 'a's → pattern "a", match "aaa"? No! ✗
Option 2: Use one 'a' → pattern "aa", match "aaa"? No! ✗
Option 3: Use two 'a's → pattern "aaa", match "aaa"? Yes! ✓
INSIGHT: This is a SEARCH problem!
We need to try different possibilities! 🎯
This screams RECURSION or DYNAMIC PROGRAMMING! 🔑
🤔 Building Intuition - The Recursive Structure
Understanding Character-by-Character Matching
Let me think about how matching works:
Compare s[i] with p[j] (character by character):
CASE 1: No special characters
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
s = "abc", p = "abc"
i=0, j=0: 'a' == 'a' ✓ → Move both forward
i=1, j=1: 'b' == 'b' ✓ → Move both forward
i=2, j=2: 'c' == 'c' ✓ → Move both forward
Done! → MATCH ✓
Simple! Just compare character by character!
CASE 2: Dot character '.'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
s = "abc", p = "a.c"
i=0, j=0: 'a' == 'a' ✓ → Move both forward
i=1, j=1: 'b' vs '.' → '.' matches anything! ✓ → Move both forward
i=2, j=2: 'c' == 'c' ✓ → Move both forward
Done! → MATCH ✓
'.' is like a normal character, but matches ANY character!
CASE 3: Star character '*' - THE HARD PART!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
s = "aab", p = "a*b"
At j=1, we see '*'!
'*' modifies 'a' (the preceding character)
"a*" means: zero or more 'a's
We have CHOICES:
Choice 1: Use zero 'a's
Skip "a*", try to match "aab" with "b"
→ Doesn't work! ✗
Choice 2: Use one or more 'a's
Match current 'a' in string
Then decide: use MORE 'a's, or move past "a*"?
This is RECURSIVE! 🎯
The Recursive Insight
Define: isMatch(i, j) = does s[i..] match p[j..]?
Base cases:
If pattern is empty (j == len(p)):
Match only if string is also empty!
return i == len(s)
If string is empty (i == len(s)):
Match only if pattern can match empty!
(This happens with patterns like "a*b*c*")
Recursive cases:
CASE 1: No '*' at p[j+1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Simple matching!
Check if current characters match:
- s[i] == p[j], OR
- p[j] == '.' (matches anything)
If they match:
isMatch(i, j) = isMatch(i+1, j+1)
(Move both forward)
If they don't match:
isMatch(i, j) = false
CASE 2: '*' at p[j+1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Complex! We have choices!
Pattern is: p[j] followed by '*'
This means: "zero or more of p[j]"
Option A: Use ZERO occurrences
Skip p[j] and '*'
isMatch(i, j) includes isMatch(i, j+2)
Option B: Use ONE OR MORE occurrences
First check: does s[i] match p[j]?
If YES:
Match s[i] with p[j]
Stay on "p[j]*" pattern (might use more!)
isMatch(i, j) includes isMatch(i+1, j)
Final: isMatch(i, j) = Option A OR Option B
This is the complete recursive structure! ✓
🔴 Approach 1: Pure Recursion - Understanding the Pattern
The Recursive Logic
Let me write the recursive function step by step:
isMatch(s, p, i, j):
BASE CASE 1: Pattern exhausted
if j == len(p):
return i == len(s) // Match only if string also done
BASE CASE 2: Check if current chars match
firstMatch = (i < len(s)) AND
(s[i] == p[j] OR p[j] == '.')
RECURSIVE CASE 1: Star at next position
if j+1 < len(p) AND p[j+1] == '*':
// Option A: Use zero occurrences (skip p[j]*)
// Option B: Use one+ occurrences (if firstMatch)
return isMatch(i, j+2) OR
(firstMatch AND isMatch(i+1, j))
RECURSIVE CASE 2: No star
else:
// Simple matching - both must match and continue
return firstMatch AND isMatch(i+1, j+1)
This is the complete algorithm! ✓
Visualizing The Recursion Tree
Example: s = "aab", p = "c*a*b"
Let me trace the recursion:
isMatch(0,0)
s[0]='a', p[0]='c'
p[1]='*' → Try both options!
Option A: Skip "c*" Option B: Use "c*"
isMatch(0,2) firstMatch? 'a'=='c'? NO ✗
s[0]='a', p[2]='a' Can't use Option B!
p[3]='*' → Try both!
Option A: Skip "a*" Option B: Use "a*"
isMatch(0,4) firstMatch? 'a'=='a'? YES ✓
s[0]='a', p[4]='b' isMatch(1,2)
'a'=='b'? NO ✗ s[1]='a', p[2]='a'
p[3]='*' → Try both!
Option A Option B
isMatch(1,4) isMatch(2,2)
s[1]='a' s[2]='b'
p[4]='b' p[2]='a'
'a'=='b'? NO✗ p[3]='*'
Try both!
A: isMatch(2,4)
s[2]='b', p[4]='b'
'b'=='b'? YES ✓
isMatch(3,5)
i=3, j=5
Both done! ✓
Result: TRUE! ✓
The path: Skip "c*" → Use two "a*" → Match "b" → Success!
Implementation
class Solution {
public boolean isMatch(String s, String p) {
return isMatchHelper(s, p, 0, 0);
}
private boolean isMatchHelper(String s, String p, int i, int j) {
// Base case: pattern exhausted
if (j == p.length()) {
return i == s.length();
}
// Check if current characters match
boolean firstMatch = (i < s.length()) &&
(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
// Case 1: Star at next position
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
// Option A: Use zero occurrences (skip pattern[j]*)
// Option B: Use one or more (if firstMatch)
return isMatchHelper(s, p, i, j + 2) ||
(firstMatch && isMatchHelper(s, p, i + 1, j));
}
// Case 2: No star - simple matching
return firstMatch && isMatchHelper(s, p, i + 1, j + 1);
}
}
Why This Is Too Slow
TIME COMPLEXITY ANALYSIS:
At each '*', we make 2 recursive calls!
Recursion tree branches exponentially!
(0,0)
/ \
(0,2) (1,0)
/ \ / \
(0,4)(1,2)(1,2)(2,0)
↑ ↑
SAME STATE called TWICE!
Number of unique states: m × n
But each state called MANY times!
Worst case: O(2^(m+n)) ❌
For s = "aaaaaaaaaaaaaaaaaa" (18 chars)
p = "a*a*a*a*a*a*a*a*a*" (18 chars)
2^36 operations! ❌
OBSERVATION:
Same (i,j) computed multiple times!
Overlapping subproblems!
This screams MEMOIZATION! 🔑
🟡 Approach 2: Memoization (Top-Down DP)
Adding The Cache
The problem with pure recursion:
We solve same (i,j) many times!
Solution:
Cache the results!
memo[i][j] = result for isMatch(i, j)
When we compute isMatch(i, j):
1. Check if already computed (in memo)
2. If yes, return cached result
3. If no, compute it, cache it, then return
This eliminates redundant computation! ✓
Implementation
class Solution {
private Boolean[][] memo;
public boolean isMatch(String s, String p) {
// Initialize memoization table
// Boolean (not boolean) to distinguish uncomputed (null) vs computed (true/false)
memo = new Boolean[s.length() + 1][p.length() + 1];
return isMatchHelper(s, p, 0, 0);
}
private boolean isMatchHelper(String s, String p, int i, int j) {
// Check memo first
if (memo[i][j] != null) {
return memo[i][j];
}
// Base case: pattern exhausted
if (j == p.length()) {
memo[i][j] = (i == s.length());
return memo[i][j];
}
// Check if current characters match
boolean firstMatch = (i < s.length()) &&
(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
boolean result;
// Case 1: Star at next position
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
// Option A: Use zero occurrences (skip pattern[j]*)
// Option B: Use one or more (if firstMatch)
result = isMatchHelper(s, p, i, j + 2) ||
(firstMatch && isMatchHelper(s, p, i + 1, j));
} else {
// Case 2: No star - simple matching
result = firstMatch && isMatchHelper(s, p, i + 1, j + 1);
}
// Cache the result
memo[i][j] = result;
return result;
}
}
Why Memoization Works
KEY INSIGHT:
Number of unique states: m × n
(m = length of string, n = length of pattern)
Each state computed AT MOST ONCE!
When we see same (i,j) again:
Return cached result in O(1)!
TIME COMPLEXITY:
Number of states: O(m × n)
Work per state: O(1) (after first computation)
Total: O(m × n) ✓
Much better than O(2^(m+n))! 🚀
SPACE COMPLEXITY:
Memo table: O(m × n)
Call stack: O(m + n)
Total: O(m × n) ✓
🟢 Approach 3: Bottom-Up DP - Building From Base Cases
Understanding The DP State
Let me think about the DP table:
dp[i][j] = does s[0..i-1] match p[0..j-1]?
Why this definition?
- s[0..i-1] means first i characters of s
- p[0..j-1] means first j characters of p
- dp[i][j] answers: do these prefixes match?
Examples:
s = "aab", p = "c*a*b"
dp[0][0] = does "" match ""? YES ✓
dp[1][1] = does "a" match "c"? NO ✗
dp[1][2] = does "a" match "c*"? YES ✓ (use zero 'c's)
dp[3][5] = does "aab" match "c*a*b"? (final answer)
This is our DP definition! ✓
Building The DP Table - Understanding Each Cell
Let me build for: s = "aa", p = "a*"
Table dimensions: (len(s)+1) × (len(p)+1) = 3 × 3
Initial state:
"" a *
"" ? ? ?
a ? ? ?
a ? ? ?
PHASE 1: Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][0]: Does "" match ""?
Both empty → YES ✓
dp[0][0] = true
dp[0][j]: Does "" match p[0..j-1]?
Empty string vs non-empty pattern
Can only match if pattern is like "a*b*c*" (all stars!)
dp[0][1]: "" vs "a" → NO ✗
dp[0][2]: "" vs "a*" → YES ✓ (zero 'a's)
How to compute dp[0][j] in general?
If p[j-1] == '*':
Can use zero of preceding element
dp[0][j] = dp[0][j-2]
Else:
dp[0][j] = false
"" a *
"" T F T
a ? ? ?
a ? ? ?
dp[i][0]: Does s[0..i-1] match ""?
Non-empty string vs empty pattern
Always NO! ✗
dp[1][0] = false
dp[2][0] = false
"" a *
"" T F T
a F ? ?
a F ? ?
PHASE 2: Fill The Table
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Now fill dp[i][j] for i > 0, j > 0
dp[1][1]: Does "a" match "a"?
Check: s[0]='a' vs p[0]='a'
No star at p[1]
Characters match? YES!
dp[1][1] = dp[0][0] = true ✓
"" a *
"" T F T
a F T ?
a F ? ?
dp[1][2]: Does "a" match "a*"?
Check: p[1]='*' (star!)
Star modifies p[0]='a'
Option A: Use zero 'a's
dp[1][2] = dp[1][0] = false
Option B: Use one or more 'a's
s[0]='a' vs p[0]='a' → Match! ✓
dp[1][2] = dp[0][2] = true ✓
Result: false OR true = true ✓
"" a *
"" T F T
a F T T
a F ? ?
dp[2][1]: Does "aa" match "a"?
Check: s[1]='a' vs p[0]='a'
No star at p[1]
Characters match? YES!
dp[2][1] = dp[1][0] = false ✗
(Previous doesn't match, so this doesn't either)
"" a *
"" T F T
a F T T
a F F ?
dp[2][2]: Does "aa" match "a*"?
Check: p[1]='*' (star!)
Option A: Use zero 'a's
dp[2][2] = dp[2][0] = false
Option B: Use one or more 'a's
s[1]='a' vs p[0]='a' → Match! ✓
dp[2][2] = dp[1][2] = true ✓
Result: false OR true = true ✓
"" a *
"" T F T
a F T T
a F F T
Final answer: dp[2][2] = true ✓
"aa" matches "a*"! ✓
The DP Recurrence - Complete Understanding
For dp[i][j], we're asking:
Does s[0..i-1] match p[0..j-1]?
CASE 1: No star at p[j-1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Simple character matching!
Check if s[i-1] matches p[j-1]:
- s[i-1] == p[j-1], OR
- p[j-1] == '.'
If they match:
dp[i][j] = dp[i-1][j-1]
(Previous prefixes must also match)
If they don't match:
dp[i][j] = false
CASE 2: Star at p[j-1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Pattern ends with X* (where X = p[j-2])
Option A: Use ZERO occurrences of X
Ignore X* entirely
dp[i][j] = dp[i][j-2]
Example: "ab" vs "abc*"
Use zero 'c's → match "ab" vs "ab"
Option B: Use ONE OR MORE occurrences of X
First check: does s[i-1] match X?
Match if: s[i-1] == p[j-2] OR p[j-2] == '.'
If match:
dp[i][j] includes dp[i-1][j]
(Match current char, stay on X*)
Example: "aaa" vs "a*"
s[2]='a' matches p[0]='a'
Check dp[2][2] (one less char, same pattern)
Final formula:
dp[i][j] = dp[i][j-2] OR (charMatch AND dp[i-1][j])
This is the complete DP recurrence! ✓
Why Forward Loops?
DEPENDENCY ANALYSIS:
dp[i][j] depends on:
- dp[i-1][j-1] (diagonal - one less from both)
- dp[i][j-2] (left - two less from pattern)
- dp[i-1][j] (up - one less from string)
All dependencies have SMALLER indices!
Visual:
j-2 j-1 j
i-1 [X]
↓ ↘
i [X] ? [i,j]
All arrows point to smaller indices!
Therefore: Fill table with FORWARD loops!
for i from 0 to m:
for j from 0 to n:
compute dp[i][j]
Dependencies are already computed! ✓
Complete Implementation
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
// dp[i][j] = does s[0..i-1] match p[0..j-1]?
boolean[][] dp = new boolean[m + 1][n + 1];
// Base case: empty string matches empty pattern
dp[0][0] = true;
// Base case: empty string vs pattern
// Can only match if pattern is like "a*b*c*"
for (int j = 2; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// Fill the table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
// Case 1: Star - two options
// Option A: Use zero occurrences
dp[i][j] = dp[i][j - 2];
// Option B: Use one or more occurrences
// Check if current chars match
if (s.charAt(i - 1) == p.charAt(j - 2) ||
p.charAt(j - 2) == '.') {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else {
// Case 2: No star - simple matching
if (s.charAt(i - 1) == p.charAt(j - 1) ||
p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
// else dp[i][j] remains false
}
}
}
return dp[m][n];
}
}
🔍 Detailed Example - Complete Walkthrough
Example: s = "aab", p = "cab"
Let me build the complete DP table!
m = 3 (aab), n = 5 (c*a*b)
Table dimensions: 4 × 6
PHASE 1: Initialize Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"" c * a * b
"" T ? ? ? ? ?
a F ? ? ? ? ?
a F ? ? ? ? ?
b F ? ? ? ? ?
dp[0][0] = true (empty matches empty)
dp[i][0] = false for all i > 0
Now compute dp[0][j] for j > 0:
dp[0][1]: "" vs "c"
Not a star, empty string doesn't match
dp[0][1] = false
dp[0][2]: "" vs "c*"
Star! Can use zero 'c's
dp[0][2] = dp[0][0] = true ✓
dp[0][3]: "" vs "c*a"
Not a star, empty doesn't match
dp[0][3] = false
dp[0][4]: "" vs "c*a*"
Star! Can use zero 'a's
dp[0][4] = dp[0][2] = true ✓
dp[0][5]: "" vs "c*a*b"
Not a star
dp[0][5] = false
"" c * a * b
"" T F T F T F
a F ? ? ? ? ?
a F ? ? ? ? ?
b F ? ? ? ? ?
PHASE 2: Fill The Table Row By Row
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROW 1 (i=1, string="a"):
dp[1][1]: "a" vs "c"
s[0]='a' vs p[0]='c'
No star, no match
dp[1][1] = false
dp[1][2]: "a" vs "c*"
Star!
Option A: zero 'c's → dp[1][0] = false
Option B: s[0]='a' vs p[0]='c'? No match
dp[1][2] = false OR false = false
dp[1][3]: "a" vs "c*a"
s[0]='a' vs p[2]='a' → Match!
No star at p[3]
dp[1][3] = dp[0][2] = true ✓
dp[1][4]: "a" vs "c*a*"
Star!
Option A: zero 'a's → dp[1][2] = false
Option B: s[0]='a' vs p[2]='a' → Match!
dp[1][4] includes dp[0][4] = true ✓
dp[1][4] = false OR true = true ✓
dp[1][5]: "a" vs "c*a*b"
s[0]='a' vs p[4]='b'
No star, no match
dp[1][5] = false
"" c * a * b
"" T F T F T F
a F F F T T F
a F ? ? ? ? ?
b F ? ? ? ? ?
ROW 2 (i=2, string="aa"):
dp[2][1]: "aa" vs "c"
No match (obviously)
dp[2][1] = false
dp[2][2]: "aa" vs "c*"
Star!
Option A: zero 'c's → dp[2][0] = false
Option B: s[1]='a' vs p[0]='c'? No
dp[2][2] = false
dp[2][3]: "aa" vs "c*a"
s[1]='a' vs p[2]='a' → Match!
dp[2][3] = dp[1][2] = false
dp[2][4]: "aa" vs "c*a*"
Star!
Option A: zero 'a's → dp[2][2] = false
Option B: s[1]='a' vs p[2]='a' → Match!
dp[2][4] includes dp[1][4] = true ✓
dp[2][4] = false OR true = true ✓
dp[2][5]: "aa" vs "c*a*b"
s[1]='a' vs p[4]='b'
No match
dp[2][5] = false
"" c * a * b
"" T F T F T F
a F F F T T F
a F F F F T F
b F ? ? ? ? ?
ROW 3 (i=3, string="aab"):
dp[3][1]: "aab" vs "c"
dp[3][1] = false
dp[3][2]: "aab" vs "c*"
Star!
Option A: zero 'c's → dp[3][0] = false
Option B: s[2]='b' vs p[0]='c'? No
dp[3][2] = false
dp[3][3]: "aab" vs "c*a"
s[2]='b' vs p[2]='a'
No match
dp[3][3] = false
dp[3][4]: "aab" vs "c*a*"
Star!
Option A: zero 'a's → dp[3][2] = false
Option B: s[2]='b' vs p[2]='a'? No
dp[3][4] = false
dp[3][5]: "aab" vs "c*a*b"
s[2]='b' vs p[4]='b' → Match! ✓
No star
dp[3][5] = dp[2][4] = true ✓
"" c * a * b
"" T F T F T F
a F F F T T F
a F F F F T F
b F F F F F T
FINAL ANSWER: dp[3][5] = TRUE ✓
"aab" matches "c*a*b"! ✓
The matching: zero 'c's + two 'a's + one 'b' = "aab" ✓
📊 Complexity Analysis
All Approaches Compared
┌──────────────┬─────────────┬──────────────┬──────────────┐
│ Approach │ Time │ Space │ Practical? │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Recursion │ O(2^(m+n)) │ O(m+n) │ NO ❌ │
│ (Approach 1) │ Exponential │ Stack │ Too slow │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Memoization │ O(m×n) │ O(m×n) │ YES ✓ │
│ (Approach 2) │ Polynomial │ Memo+Stack │ Good │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Bottom-Up DP │ O(m×n) │ O(m×n) │ YES ✓ │
│ (Approach 3) │ Polynomial │ Table only │ Best │
└──────────────┴─────────────┴──────────────┴──────────────┘
m = length of string s
n = length of pattern p
Detailed Time Complexity
APPROACH 1 - Pure Recursion:
At each '*':
Two options (zero vs one-or-more)
Two recursive calls
Branching factor: ~2
Tree height: m + n
Total nodes: O(2^(m+n)) ❌
For s = "aaaaaaaaaa" (10 'a's)
p = "a*a*a*a*a*" (10 chars)
2^20 ≈ 1 million calls! ❌
APPROACH 2 - Memoization:
Number of unique states: m × n
Each state computed once: O(1) work
Total: O(m × n) ✓
For s = 20 chars, p = 20 chars:
20 × 20 = 400 states ✓
APPROACH 3 - Bottom-Up DP:
Nested loops: i from 0 to m, j from 0 to n
Each cell: O(1) work
Total: O(m × n) ✓
Same as memoization! ✓
Detailed Space Complexity
APPROACH 1 - Pure Recursion:
Call stack depth: O(m + n)
No extra storage
Total: O(m + n)
But impractical due to time! ❌
APPROACH 2 - Memoization:
Memo table: (m+1) × (n+1) Booleans
Size: O(m × n)
Call stack: O(m + n)
Total: O(m × n) ✓
APPROACH 3 - Bottom-Up DP:
DP table: (m+1) × (n+1) booleans
Size: O(m × n)
No recursion stack!
Total: O(m × n) ✓
SPACE OPTIMIZATION:
Can we use O(n) space?
For DP, only need current and previous row
But loses clarity
For most interviews: O(m × n) is fine! ✓
🎯 Pattern Recognition
The Problem Family
PATTERN MATCHING PROBLEMS:
All involve matching strings with special rules!
1. Problem 243: Regular Expression Matching
Rules: '.' (any char), '*' (zero or more)
Approach: DP with choices
2. Wildcard Matching (Problem 44):
Rules: '?' (any char), '*' (any sequence)
Approach: Similar DP
3. Edit Distance (Problem 72):
Rules: insert, delete, replace
Approach: DP with operations
4. String Interleaving (Problem 97):
Rules: merge two strings
Approach: DP with paths
Common pattern:
- Two strings comparison
- Character-by-character decisions
- Multiple choices at each step
- Optimal substructure
- DP solution! 🔑
When To Recognize This Pattern
TRIGGER WORDS:
✓ "Pattern matching"
✓ "Regular expression"
✓ "Special characters"
✓ "Wildcard"
✓ "Match entire string"
PROBLEM STRUCTURE:
- Two strings (text and pattern)
- Special characters with rules
- Need complete matching
- Yes/no answer
SOLUTION APPROACH:
1. Identify choices at each position
2. Define recursive structure
3. Add memoization
4. Convert to bottom-up DP
This is a MASTER PATTERN! ✓
💻 Complete Working Code
class Solution {
// Approach 3: Bottom-Up DP (Most efficient)
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
// Base case
dp[0][0] = true;
// Pattern like "a*b*c*" can match empty string
for (int j = 2; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// Fill table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
// Star case
dp[i][j] = dp[i][j - 2]; // Zero occurrences
if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
dp[i][j] = dp[i][j] || dp[i - 1][j]; // One or more
}
} else {
// Regular character or '.'
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.isMatch("aa", "a")); // false
System.out.println(sol.isMatch("aa", "a*")); // true
System.out.println(sol.isMatch("ab", ".*")); // true
System.out.println(sol.isMatch("aab", "c*a*b")); // true
}
}
🔑 Key Insights Summary
The Learning Journey
CRAWL (Understanding):
✓ What are '.' and '*'?
✓ Why is matching hard?
✓ What are the choices?
WALK (Building):
✓ Recursive structure
✓ Base cases
✓ Two main cases (star vs no star)
RUN (Mastery):
✓ Memoization
✓ Bottom-up DP
✓ Complete implementation
Natural progression! 🎯
The Core Understanding
1. WHY DP?
Multiple choices at each '*'
Overlapping subproblems
2. WHAT are the choices?
Star: zero vs one-or-more
3. HOW to handle star?
Option A: Skip it (zero)
Option B: Use it (if match)
4. WHEN to check match?
s[i-1] == p[j-1] OR p[j-1] == '.'
5. WHERE are dependencies?
dp[i-1][j-1], dp[i][j-2], dp[i-1][j]
Mental Model
Think of it as PATH EXPLORATION:
At each step:
- No star? One path (match or fail)
- Star? Two paths (use zero vs use one+)
DP finds if ANY path succeeds!
Visual:
Start → choices → choices → ... → End
↓ ↓
branches everywhere
DP explores ALL branches efficiently! ✓
📝 Quick Revision
🎯 Core Rules
'.' → matches ANY single character
'*' → matches ZERO OR MORE of preceding
⚡Quick Implementation
public class Solution {
public boolean isMatch(String s, String p) {
// return recursive(s, p, 0, 0);
// Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
// return topDown(s, p, 0, 0, memo);
return bottomUp(s, p);
}
private boolean bottomUp(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
// base case 1: empty string always match empty pattern
dp[0][0] = true;
// base case 2: empty string and non-empty pattern
// 1st row. This is when pattern consists of like "c*a*b*"
// which matches an empty string.
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// base case 3: non-empty string and empty pattern
// This will be always false which is by default.
// step 1: start trying from i = 1 and j = 1
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
// GOTCHA: we need to check * for the current character
// in bottom up which is different from top down
if (p.charAt(j - 1) == '*') {
boolean skipStar = dp[i][j - 2];
// GOTCHA
boolean singleCharMatch = s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.';
boolean includeStar = singleCharMatch && dp[i - 1][j];
dp[i][j] = skipStar || includeStar;
} else {
boolean singleCharMatch = s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.';
dp[i][j] = singleCharMatch && dp[i - 1][j - 1];
}
}
}
return dp[s.length()][p.length()];
}
private boolean topDown(String s, String p, int i, int j, Boolean[][] memo) {
if (j == p.length()) {
return i == s.length();
}
if (memo[i][j] != null) {
return memo[i][j];
}
boolean singleCharMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
boolean skipStar = topDown(s, p, i, j + 2, memo);
boolean includeStar = singleCharMatch && topDown(s, p, i + 1, j, memo);
return memo[i][j] = skipStar || includeStar;
}
return memo[i][j] = singleCharMatch && topDown(s, p, i + 1, j + 1, memo);
}
private boolean recursive(String s, String p, int i, int j) {
// step 3: base case (pattern exhausted)
if (j == p.length()) {
// return true only of string also got exhausted
return i == s.length();
}
// step 1: single char match (without and with .) - see first example
// Either chars at i and j should match or pattern needs to have .
boolean singleCharMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
// Step 2: if we have a * that is succeeding the current char in pattern
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
// step 2a: as * can represent 0 characters also, can skip it completely
boolean skipStar = recursive(s, p, i, j + 2);
// step 2b: * may represent one to many characters.
// Match for one character for now and call recursively keeping j here only.
// Match for one char is already in singleCharMatch
boolean includeStar = singleCharMatch && recursive(s, p, i + 1, j);
return skipStar || includeStar;
}
// step 3: if we do not have a * after index j in the pattern
return singleCharMatch && recursive(s, p, i + 1, j + 1);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.isMatch("abc", "a.c") == true);
System.out.println(s.isMatch("aa", "a") == false);
System.out.println(s.isMatch("aa", "a*") == true);
System.out.println(s.isMatch("ab", ".*") == true);
}
}
🔑 Key Patterns
Star handling:
- Option A: Always available (zero)
- Option B: Only if chars match (one+)
Base cases:
- dp[0][0] = true
- dp[0][j] = true if p[0..j-1] = "X*Y*..."
- dp[i][0] = false for i > 0
🎪 Memory Aid
"Star gives choices"
"Try zero or try more"
"DP finds the way"
Complexity: O(m×n) time and space
🎉 Congratulations!
You've mastered through baby steps:
- ✅ CRAWL: Understanding special characters
- ✅ WALK: Building recursive structure
- ✅ RUN: Complete DP mastery
- ✅ All three approaches explained
- ✅ Complete table walkthrough
- ✅ Pattern connections made
- ✅ True comprehensive understanding
Another hard problem conquered! 🚀✨