244. Wildcard Matching
🔗 LeetCode Problem: 44. Wildcard Matching
📊 Difficulty: Hard
🏷️ Topics: Dynamic Programming, String, DP - Strings, Greedy
Problem Statement
Given an input string s and a pattern p, implement wildcard pattern matching with support for '?' and '*' where:
'?'Matches any single character.'*'Matches any sequence of characters (including the empty sequence).
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 = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'b', which does not match 'a'.
Example 4:
Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input: s = "acdcb", p = "a*c?b"
Output: true
Constraints:
- 0 <= s.length, p.length <= 2000
- s contains only lowercase English letters.
- p contains only lowercase English letters, '?' or '*'.
🧒 Let's Build Understanding from Absolute Scratch
What Does This Problem REALLY Ask?
Forget "wildcard" 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 = "*"
Question: What does '*' mean?
Let me think:
'*' matches ANY SEQUENCE of characters
ANY means: zero chars, one char, two chars, ...
Can '*' match "aa"?
Use two characters: "aa" ✓
Result: MATCH ✓
So '*' is very POWERFUL - it can match anything! 🎯
Understanding the Wildcard Characters
CHARACTER 1: '?' (question mark)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
'?' 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)
s = "ab", p = "??" → Match! ✓ (two '?' match two chars)
Think of '?' as a wildcard for EXACTLY ONE character!
This is SIMPLE! ✓
CHARACTER 2: '*' (star)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
'*' matches ANY SEQUENCE of characters (including empty!)
Examples:
"*" can match:
"" (empty) ✓
"a" (one char) ✓
"ab" (two chars) ✓
"abc" (three chars) ✓
"anything" (any string!) ✓
s = "hello", p = "*" → Match! ✓
s = "", p = "*" → Match! ✓ (empty sequence)
"a*" can match:
"a" (then empty) ✓
"ab" (a + one char) ✓
"abc" (a + two chars) ✓
"axyz" (a + three chars) ✓
s = "abc", p = "a*" → Match! ✓
"*b" can match:
"b" (empty + b) ✓
"ab" (one char + b) ✓
"xyzb" (three chars + b) ✓
s = "hello_world_b", p = "*b" → Match! ✓
This is VERY POWERFUL! 🔑
Comparing With Regular Expression (Problem 243)
Let me compare to help understand:
PROBLEM 243: Regular Expression Matching
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
'.' → matches any single character
'*' → matches zero or more of PRECEDING element
Example: "a*" in regex
Means: zero or more 'a's
Matches: "", "a", "aa", "aaa", ...
Does NOT match: "b", "ab", "ba"
'*' is tied to the character BEFORE it!
PROBLEM 244: Wildcard Matching
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
'?' → matches any single character (same as '.')
'*' → matches ANY SEQUENCE (much more powerful!)
Example: "*" in wildcard
Means: any sequence of any characters
Matches: "", "a", "ab", "xyz", "anything!"
'*' works INDEPENDENTLY!
KEY DIFFERENCE:
Regex '*': tied to preceding char → limited
Wildcard '*': independent → very flexible! 🔑
Wildcard is actually SIMPLER conceptually!
But still hard to implement efficiently!
🤔 Why Is This Problem Hard?
The Challenge of '*'
The problem: '*' gives us INFINITE choices!
Example: s = "abc", p = "*c"
'*' can match:
0 chars: "", try to match "abc" with "c" → NO ✗
1 char: "a", try to match "bc" with "c" → NO ✗
2 chars: "ab", try to match "c" with "c" → YES! ✓
3 chars: "abc", try to match "" with "c" → NO ✗
We don't know which choice is correct!
Another example: s = "abcde", p = "*c*"
First '*' can match: "", "a", "ab", "abc", "abcd", "abcde"
Second '*' can match: "", "d", "de", "e"
Combinations: Many possibilities!
Which one is correct? 🤔
We need to TRY different possibilities!
Example: s = "aa", p = "**"
First '*' matches: "", "a", "aa"
Second '*' matches: remaining
If first '*' matches "": second '*' must match "aa" ✓
If first '*' matches "a": second '*' must match "a" ✓
If first '*' matches "aa": second '*' must match "" ✓
All work! But we only need to find ONE that works!
INSIGHT: This is a SEARCH problem!
Try different possibilities until one works!
This screams RECURSION or DP! 🔑
Multiple Stars Make It Complex
Example: s = "abcde", p = "a*b*c*d*e"
We have FOUR stars!
Each star has multiple choices:
First '*': match "", "b", "bc", "bcd", ...
Second '*': match "", "c", "cd", ...
Third '*': match "", "d", ...
Fourth '*': match "", "e", ...
Total combinations: HUGE! 😰
Naive approach:
Try all combinations
Time: Exponential! ❌
Smart approach:
Use DP to avoid recomputation!
Time: Polynomial! ✓
This is why we need DP! 🎯
💡 Building The Recursive Structure
Understanding Character-by-Character Matching
Let me think about matching step by step:
Compare s[i] with p[j] (character by character):
CASE 1: Regular character (no wildcards)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
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!
CASE 2: '?' 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 regular character that always matches!
CASE 3: '*' character - THE HARD PART!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
s = "abc", p = "*c"
At j=0, we see '*'!
'*' can match: "", "a", "ab", "abc"
We have CHOICES:
Choice 1: '*' matches empty ""
Try to match "abc" with "c"
→ Doesn't work! ✗
Choice 2: '*' matches "a"
Try to match "bc" with "c"
→ Doesn't work! ✗
Choice 3: '*' matches "ab"
Try to match "c" with "c"
→ Works! ✓
We found a match!
But how do we try these choices systematically? 🤔
The Recursive Insight
Define: isMatch(i, j) = does s[i..] match p[j..]?
What this means:
- s[i..] is the substring of s starting from index i
- p[j..] is the substring of p starting from index j
- Return true if they match, false otherwise
Base cases:
BASE CASE 1: Both exhausted
if i == len(s) AND j == len(p):
return true // Both done, perfect match!
BASE CASE 2: String exhausted, pattern remains
if i == len(s) AND j < len(p):
Pattern must be all '*' to match empty string!
Example: s="", p="***" → true ✓
Example: s="", p="a*" → false ✗
BASE CASE 3: Pattern exhausted, string remains
if i < len(s) AND j == len(p):
return false // String has more, no pattern to match!
Recursive cases:
CASE 1: Pattern has '*'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
p[j] == '*'
'*' can match any sequence!
Two main options:
Option A: '*' matches EMPTY sequence
Skip the '*', continue matching
isMatch(i, j+1)
Example: s="abc", p="*abc"
'*' matches empty, then "abc" matches "abc"
Option B: '*' matches ONE OR MORE characters
Use current character, keep '*' for more
isMatch(i+1, j)
Example: s="abc", p="*c"
'*' matches 'a', try to match "bc" with "*c"
'*' matches 'b', try to match "c" with "*c"
'*' done, match "c" with "c" ✓
Result: isMatch(i, j) = Option A OR Option B
CASE 2: Pattern has '?' or regular character
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
p[j] == '?' OR p[j] == s[i]
Characters match!
isMatch(i, j) = isMatch(i+1, j+1)
(Move both forward)
Characters don't match:
isMatch(i, j) = false
This is the complete recursive structure! ✓
🔴 Approach 1: Pure Recursion - Understanding the Pattern
The Recursive Logic
Let me write the recursive function:
isMatch(s, p, i, j):
BASE CASE 1: Both exhausted
if i == len(s) AND j == len(p):
return true
BASE CASE 2: Pattern exhausted, string remains
if j == len(p):
return false // String still has characters
BASE CASE 3: String exhausted, pattern remains
if i == len(s):
// Check if remaining pattern is all '*'
for k from j to len(p):
if p[k] != '*':
return false
return true
RECURSIVE CASE 1: Pattern has '*'
if p[j] == '*':
// Option A: Match empty
// Option B: Match one or more
return isMatch(i, j+1) OR isMatch(i+1, j)
RECURSIVE CASE 2: Pattern has '?' or matching char
if p[j] == '?' OR p[j] == s[i]:
return isMatch(i+1, j+1)
else:
return false
This is the complete algorithm! ✓
Visualizing The Recursion Tree
Example: s = "ab", p = "*b"
Let me trace the recursion:
isMatch(0,0)
s[0]='a', p[0]='*'
'*' → Try both options!
Option A: Match empty Option B: Match 'a'
isMatch(0,1) isMatch(1,0)
s[0]='a', p[1]='b' s[1]='b', p[0]='*'
'a'=='b'? NO ✗ '*' → Try both!
A: isMatch(1,1)
s[1]='b', p[1]='b'
'b'=='b'? YES ✓
isMatch(2,2)
Both done! ✓
Result: TRUE! ✓
The path: '*' matches 'a' → 'b' matches 'b' → Success!
Another example: s = "abc", p = "*c"
isMatch(0,0)
s[0]='a', p[0]='*'
A: isMatch(0,1) B: isMatch(1,0)
s[0]='a', p[1]='c' s[1]='b', p[0]='*'
NO ✗
A: isMatch(1,1) B: isMatch(2,0)
s[1]='b', p[1]='c' s[2]='c', p[0]='*'
NO ✗
A: isMatch(2,1)
s[2]='c', p[1]='c'
YES ✓
isMatch(3,2)
Done! ✓
Result: TRUE! ✓
Path: '*' matches "ab" → 'c' matches 'c' ✓
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: Both exhausted
if (i == s.length() && j == p.length()) {
return true;
}
// Base case: Pattern exhausted, string remains
if (j == p.length()) {
return false;
}
// Base case: String exhausted, pattern remains
if (i == s.length()) {
// Check if remaining pattern is all '*'
for (int k = j; k < p.length(); k++) {
if (p.charAt(k) != '*') {
return false;
}
}
return true;
}
// Case 1: Pattern has '*'
if (p.charAt(j) == '*') {
// Option A: Match empty sequence
// Option B: Match one or more characters
return isMatchHelper(s, p, i, j + 1) ||
isMatchHelper(s, p, i + 1, j);
}
// Case 2: Pattern has '?' or matching character
if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) {
return isMatchHelper(s, p, i + 1, j + 1);
}
// No match
return false;
}
}
Why This Is Too Slow
TIME COMPLEXITY ANALYSIS:
At each '*', we make 2 recursive calls!
Recursion tree branches exponentially!
(0,0)
/ \
(0,1) (1,0)
/ \ / \
(0,2)(1,1)(1,1)(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 = "aaaaaaaaaaaaaa" (14 'a's)
p = "**************" (14 '*'s)
2^28 ≈ 268 million 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 (O(1)!)
3. If no, compute it, cache it, then return
This eliminates redundant computation! ✓
Why this works:
- Number of states: m × n
- Each state computed AT MOST once
- Total time: O(m × n) ✓
Much better than exponential! 🚀
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
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: Both exhausted
if (i == s.length() && j == p.length()) {
memo[i][j] = true;
return true;
}
// Base case: Pattern exhausted, string remains
if (j == p.length()) {
memo[i][j] = false;
return false;
}
// Base case: String exhausted, pattern remains
if (i == s.length()) {
// Check if remaining pattern is all '*'
for (int k = j; k < p.length(); k++) {
if (p.charAt(k) != '*') {
memo[i][j] = false;
return false;
}
}
memo[i][j] = true;
return true;
}
boolean result;
// Case 1: Pattern has '*'
if (p.charAt(j) == '*') {
// Option A: Match empty
// Option B: Match one or more
result = isMatchHelper(s, p, i, j + 1) ||
isMatchHelper(s, p, i + 1, j);
}
// Case 2: Pattern has '?' or matching character
else if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) {
result = isMatchHelper(s, p, i + 1, j + 1);
}
// No match
else {
result = false;
}
// 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) for most cases
Base case check: O(n) in worst case
Total: O(m × n) ✓
SPACE COMPLEXITY:
Memo table: O(m × n)
Call stack: O(m + n)
Total: O(m × n) ✓
Much better than O(2^(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]?
What this means:
- 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 = "ab", p = "*b"
dp[0][0] = does "" match ""? YES ✓
dp[0][1] = does "" match "*"? YES ✓ (matches empty)
dp[1][1] = does "a" match "*"? YES ✓
dp[2][2] = does "ab" match "*b"? (final answer)
This is our DP definition! ✓
Building The DP Table - Understanding Each Cell
Let me build for: s = "ab", p = "*b"
Table dimensions: (len(s)+1) × (len(p)+1) = 3 × 3
Initial state:
"" * b
"" ? ? ?
a ? ? ?
b ? ? ?
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 all '*'!
dp[0][1]: "" vs "*"
'*' can match empty! ✓
dp[0][1] = true
dp[0][2]: "" vs "*b"
'*' can match empty, but 'b' cannot!
dp[0][2] = false
General rule:
if p[j-1] == '*':
dp[0][j] = dp[0][j-1] // '*' matches empty
else:
dp[0][j] = false
"" * b
"" T T F
a ? ? ?
b ? ? ?
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
"" * b
"" T T F
a F ? ?
b F ? ?
PHASE 2: Fill The Table
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Now fill dp[i][j] for i > 0, j > 0
dp[1][1]: Does "a" match "*"?
p[0]='*' (star!)
Option A: '*' matches empty
dp[1][1] = dp[1][0] = false
Option B: '*' matches 'a'
dp[1][1] = dp[0][1] = true ✓
Result: false OR true = true ✓
"" * b
"" T T F
a F T ?
b F ? ?
dp[1][2]: Does "a" match "*b"?
p[1]='b' (not star, not ?)
s[0]='a' vs p[1]='b'
'a' != 'b' → NO MATCH
dp[1][2] = false
"" * b
"" T T F
a F T F
b F ? ?
dp[2][1]: Does "ab" match "*"?
p[0]='*' (star!)
Option A: '*' matches empty
dp[2][1] = dp[2][0] = false
Option B: '*' matches "a" or "ab"
dp[2][1] = dp[1][1] = true ✓
Result: false OR true = true ✓
"" * b
"" T T F
a F T F
b F T ?
dp[2][2]: Does "ab" match "*b"?
p[1]='b' (not star, not ?)
s[1]='b' vs p[1]='b'
'b' == 'b' → MATCH! ✓
dp[2][2] = dp[1][1] = true ✓
"" * b
"" T T F
a F T F
b F T T
FINAL ANSWER: dp[2][2] = TRUE ✓
"ab" matches "*b"! ✓
The matching: '*' matches 'a' + 'b' matches 'b' ✓
The DP Recurrence - Complete Understanding
For dp[i][j], we're asking:
Does s[0..i-1] match p[0..j-1]?
CASE 1: Pattern has '*'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
p[j-1] == '*'
'*' can match any sequence!
Option A: '*' matches EMPTY sequence
Ignore '*'
dp[i][j] = dp[i][j-1]
Example: "ab" vs "a*"
'*' matches empty → check "ab" vs "a"
Option B: '*' matches ONE OR MORE characters
Use one character from string
Keep '*' for more matching
dp[i][j] = dp[i-1][j]
Example: "ab" vs "*"
'*' matches 'a' → check "b" vs "*"
'*' matches 'b' → check "" vs "*" → YES!
Final formula:
dp[i][j] = dp[i][j-1] OR dp[i-1][j]
CASE 2: Pattern has '?'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
p[j-1] == '?'
'?' matches ANY single character!
Always matches current character:
dp[i][j] = dp[i-1][j-1]
Example: "ab" vs "?b"
'?' matches 'a' → check "b" vs "b" ✓
CASE 3: Pattern has regular character
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
p[j-1] is a regular character
Check if it matches current character:
if s[i-1] == p[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = false
Example: "ab" vs "ab"
'a' == 'a' → check "b" vs "b"
'b' == 'b' → check "" vs "" → YES!
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-1] (left - one less from pattern)
- dp[i-1][j] (up - one less from string)
All dependencies have SMALLER indices!
Visual:
j-1 j
i-1 [X] [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 all '*'
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// 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: Match empty (ignore *)
// Option B: Match one or more
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(j - 1) == '?' ||
p.charAt(j - 1) == s.charAt(i - 1)) {
// Case 2: '?' or matching character
dp[i][j] = dp[i - 1][j - 1];
}
// else: dp[i][j] remains false (no match)
}
}
return dp[m][n];
}
}
🔍 Detailed Example - Complete Walkthrough
Example: s = "adceb", p = "ab"
Let me build the complete DP table!
m = 5 (adceb), n = 4 (*a*b)
Table dimensions: 6 × 5
PHASE 1: Initialize Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"" * a * b
"" T ? ? ? ?
a F ? ? ? ?
d F ? ? ? ?
c F ? ? ? ?
e F ? ? ? ?
b F ? ? ? ?
dp[0][0] = true
dp[i][0] = false for all i > 0
dp[0][j]:
dp[0][1]: "" vs "*" → '*' matches empty → true ✓
dp[0][2]: "" vs "*a" → 'a' doesn't match empty → false
dp[0][3]: "" vs "*a*" → '*' matches empty → dp[0][2] = false
dp[0][4]: "" vs "*a*b" → 'b' doesn't match → false
"" * a * b
"" T T F F F
a F ? ? ? ?
d F ? ? ? ?
c F ? ? ? ?
e F ? ? ? ?
b F ? ? ? ?
PHASE 2: Fill Row By Row
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROW 1 (i=1, s="a"):
dp[1][1]: "a" vs "*"
'*' → Option A: dp[1][0]=F, Option B: dp[0][1]=T
Result: false OR true = true ✓
dp[1][2]: "a" vs "*a"
'a' == 'a' → dp[1][2] = dp[0][1] = true ✓
dp[1][3]: "a" vs "*a*"
'*' → Option A: dp[1][2]=T, Option B: dp[0][3]=F
Result: true OR false = true ✓
dp[1][4]: "a" vs "*a*b"
'a' != 'b' → false
"" * a * b
"" T T F F F
a F T T T F
d F ? ? ? ?
c F ? ? ? ?
e F ? ? ? ?
b F ? ? ? ?
ROW 2 (i=2, s="ad"):
dp[2][1]: "ad" vs "*"
'*' → Option A: dp[2][0]=F, Option B: dp[1][1]=T
Result: true ✓
dp[2][2]: "ad" vs "*a"
'd' != 'a' → false
dp[2][3]: "ad" vs "*a*"
'*' → Option A: dp[2][2]=F, Option B: dp[1][3]=T
Result: true ✓
dp[2][4]: "ad" vs "*a*b"
'd' != 'b' → false
"" * a * b
"" T T F F F
a F T T T F
d F T F T F
c F ? ? ? ?
e F ? ? ? ?
b F ? ? ? ?
ROW 3 (i=3, s="adc"):
dp[3][1]: "adc" vs "*"
'*' → true ✓
dp[3][2]: "adc" vs "*a"
'c' != 'a' → false
dp[3][3]: "adc" vs "*a*"
'*' → Option A: dp[3][2]=F, Option B: dp[2][3]=T
Result: true ✓
dp[3][4]: "adc" vs "*a*b"
'c' != 'b' → false
"" * a * b
"" T T F F F
a F T T T F
d F T F T F
c F T F T F
e F ? ? ? ?
b F ? ? ? ?
ROW 4 (i=4, s="adce"):
dp[4][1]: "adce" vs "*"
'*' → true ✓
dp[4][2]: "adce" vs "*a"
'e' != 'a' → false
dp[4][3]: "adce" vs "*a*"
'*' → Option A: dp[4][2]=F, Option B: dp[3][3]=T
Result: true ✓
dp[4][4]: "adce" vs "*a*b"
'e' != 'b' → false
"" * a * b
"" T T F F F
a F T T T F
d F T F T F
c F T F T F
e F T F T F
b F ? ? ? ?
ROW 5 (i=5, s="adceb"):
dp[5][1]: "adceb" vs "*"
'*' → true ✓
dp[5][2]: "adceb" vs "*a"
'b' != 'a' → false
dp[5][3]: "adceb" vs "*a*"
'*' → Option A: dp[5][2]=F, Option B: dp[4][3]=T
Result: true ✓
dp[5][4]: "adceb" vs "*a*b"
'b' == 'b' → dp[5][4] = dp[4][3] = true ✓
"" * a * b
"" T T F F F
a F T T T F
d F T F T F
c F T F T F
e F T F T F
b F T F T T
FINAL ANSWER: dp[5][4] = TRUE ✓
"adceb" matches "*a*b"! ✓
The matching:
First '*' matches ""
'a' matches 'a'
Second '*' matches "dce"
'b' matches 'b'
Pattern: "" + "a" + "dce" + "b" = "adceb" ✓
📊 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 (empty vs one-or-more)
Two recursive calls
Branching factor: ~2
Tree height: m + n
Total nodes: O(2^(m+n)) ❌
For s = "aaaaaaaaaaaa" (12 'a's)
p = "************" (12 '*'s)
2^24 ≈ 16 million calls! ❌
APPROACH 2 - Memoization:
Number of unique states: m × n
Each state computed once: O(1) work
Total: O(m × n) ✓
For s = 100 chars, p = 100 chars:
100 × 100 = 10,000 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?
YES! Only need previous row!
boolean[] prev = new boolean[n+1];
boolean[] curr = new boolean[n+1];
For each i:
Compute curr from prev
prev = curr
Space: O(n) ✓
But loses table for debugging
For interviews: O(m × n) is clearer! ✓
🎯 Pattern Recognition
Comparison With Problem 243
PROBLEM 243: Regular Expression Matching
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Wildcards:
'.' → matches any single character
'*' → matches zero or more of PRECEDING element
Example: "a*" matches "", "a", "aa", "aaa"
".*" matches anything
Key: '*' is TIED to preceding character!
PROBLEM 244: Wildcard Matching
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Wildcards:
'?' → matches any single character (same as '.')
'*' → matches ANY SEQUENCE (much simpler!)
Example: "*" matches anything
"*a*" matches strings with 'a' somewhere
Key: '*' is INDEPENDENT!
COMPARISON:
Similarity:
- Both use DP
- Both have overlapping subproblems
- Both O(m × n) time
- Very similar structure!
Difference:
- Regex '*' is more complex (tied to prev char)
- Wildcard '*' is simpler (independent)
- Wildcard is actually EASIER conceptually!
Both are SAME PATTERN! 🔑
The Problem Family
PATTERN MATCHING PROBLEMS:
All involve matching with special rules!
1. Problem 243: Regular Expression Matching
Rules: '.', '*' (tied to prev)
Complexity: Hard
2. Problem 244: Wildcard Matching
Rules: '?', '*' (independent)
Complexity: Hard (but simpler!)
3. Edit Distance (Problem 72):
Rules: insert, delete, replace
Approach: DP
4. String Interleaving (Problem 97):
Rules: merge two strings
Approach: DP
Common pattern:
- Two strings
- Character decisions
- Multiple choices
- Optimal substructure
- DP solution! 🔑
When To Recognize This Pattern
TRIGGER WORDS:
✓ "Pattern matching"
✓ "Wildcard"
✓ "Special characters"
✓ "Match entire string"
✓ "Sequence matching"
PROBLEM STRUCTURE:
- Two strings (text and pattern)
- Special characters with rules
- Need complete matching
- Yes/no answer
SOLUTION APPROACH:
1. Identify choices
2. Define recursive structure
3. Add memoization
4. Convert to bottom-up DP
5. Optimize space (optional)
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;
// Empty string vs pattern (pattern must be all '*')
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
// Star: match empty OR match one or more
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(j - 1) == '?' ||
p.charAt(j - 1) == s.charAt(i - 1)) {
// '?' or matching character
dp[i][j] = dp[i - 1][j - 1];
}
// else: dp[i][j] remains false
}
}
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", "*")); // true
System.out.println(sol.isMatch("cb", "?a")); // false
System.out.println(sol.isMatch("adceb", "*a*b")); // true
System.out.println(sol.isMatch("acdcb", "a*c?b")); // true
}
}
🔑 Key Insights Summary
The Learning Journey
CRAWL (Understanding):
✓ What are '?' and '*'?
✓ Why is matching hard?
✓ Comparison with regex
✓ Understanding choices
WALK (Building):
✓ Recursive structure
✓ Base cases
✓ Two main cases (star vs others)
✓ Adding memoization
RUN (Mastery):
✓ Bottom-up DP
✓ Complete table construction
✓ Cell-by-cell understanding
✓ Pattern recognition
Natural baby-to-expert progression! 🎯
The Core Understanding
1. WHY DP?
'*' gives multiple choices
Overlapping subproblems
2. WHAT are the choices?
Star: empty vs one-or-more
3. HOW to handle star?
Option A: Match empty (skip *)
Option B: Match one+ (stay on *)
4. WHEN to check match?
'?' always matches
Regular char: s[i-1] == p[j-1]
5. WHERE are dependencies?
dp[i-1][j-1], dp[i][j-1], dp[i-1][j]
Mental Model
Think of '*' as GREEDY MATCHING:
'*' tries to match as much as possible!
Start with empty:
If works → done!
If not → try more!
Keep trying until:
- Something works ✓
- Nothing works ✗
DP efficiently tries all possibilities! ✓
📝 Quick Revision
🎯 Core Rules
'?' → matches ANY single character
'*' → matches ANY SEQUENCE (including empty)
⚡ 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];
// dp[i][j] => result of matching from s[...i] to p[...j]
// base case 1 - empty string and empty pattern
dp[0][0] = true;
// base case 2 - non-empty string and empty pattern
// always false - anyways false by default
// base case 3 - empty string and non-empty pattern
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
} else {
dp[0][j] = false;
}
}
// Exactly same as top down or recursive approaches
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
boolean choice1 = dp[i][j - 1];
boolean choice2 = dp[i - 1][j];
dp[i][j] = choice1 || choice2;
} else 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] = false;
}
}
}
return dp[s.length()][p.length()];
}
private boolean topDown(String s, String p, int i, int j, Boolean[][] memo) {
if (i == s.length() && j == p.length()) {
return true;
}
if (j == p.length()) {
return false;
}
if (i == s.length()) {
while (j < p.length()) {
if (p.charAt(j) != '*') {
return false;
}
j++;
}
return true;
}
if (memo[i][j] != null) {
return memo[i][j];
}
if (p.charAt(j) == '*') {
boolean choice1 = topDown(s, p, i, j + 1, memo);
boolean choice2 = topDown(s, p, i + 1, j, memo);
return memo[i][j] = choice1 || choice2;
}
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
return memo[i][j] = topDown(s, p, i + 1, j + 1, memo);
}
return memo[i][j] = false;
}
private boolean recursive(String s, String p, int i, int j) {
// Step 3: base case 1 (both exhausted)
if (i == s.length() && j == p.length()) {
return true;
}
// Step 4: base case 2 (empty pattern, still string left)
if (j == p.length()) {
return false;
}
// Step 5: base case 3 (empty string, still pattern left)
if (i == s.length()) {
while (j < p.length()) {
if (p.charAt(j) != '*') {
return false;
}
j++;
}
return true;
}
// Step 1:
// case 1: '*' character
// s = "abc", p = "*c"
// Choice 1: '*' matches empty "" (do not consider * itself)
// Choice 2: '*' matches "a", "ab" etc (keep * still for matching next
// characters)
if (p.charAt(j) == '*') {
boolean choice1 = recursive(s, p, i, j + 1);
boolean choice2 = recursive(s, p, i + 1, j);
return choice1 || choice2;
}
// Step 2:
// case 2 and 3: regular character and '?'
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
return recursive(s, p, i + 1, j + 1);
}
return false;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.isMatch("aa", "a") == false);
System.out.println(s.isMatch("aa", "*") == true);
System.out.println(s.isMatch("cb", "?a") == false);
System.out.println(s.isMatch("adceb", "*a*b") == true);
System.out.println(s.isMatch("acdcb", "a*c?b") == false);
System.out
.println(s.isMatch("abbaaaabbbbbababbbbbbbbaaabaabbabaabbaaabbbbabbbbab", "a*aaba***b**a*a********b") == true);
}
}
🔑 Key Patterns
Star handling:
- Always try empty first
- Then try matching more
Base cases:
- dp[0][0] = true
- dp[0][j] = true if p[0..j-1] all '*'
- dp[i][0] = false for i > 0
🎪 Memory Aid
"Star matches anything"
"Try empty or try more"
"DP finds the way"
Complexity: O(m×n) time and space
🎉 Congratulations!
You've mastered through baby steps:
- ✅ CRAWL: Understanding wildcards
- ✅ WALK: Building recursive structure
- ✅ RUN: Complete DP mastery
- ✅ All three approaches explained
- ✅ Complete table walkthrough
- ✅ Comparison with regex matching
- ✅ Pattern connections made
- ✅ True comprehensive understanding
Another hard problem conquered with textbook-style learning! 🚀✨