Wildcard Matching
Match a string against a pattern with '?' and '*' using a 2D DP table: a star matches the empty sequence or eats one more letter.
Problem Understanding
Wildcard Matching: match a string s against a pattern p where ? matches any single letter and * matches any sequence of letters, including the empty one. The match must cover the whole string.
Examples: s = "aa", p = "a" is false; p = "*" is true; s = "cb", p = "?a" is false.
The Intuition: A Star Either Stops or Eats One More
Ask whether the first i letters of s match the first j characters of p, and look at the last pattern character:
- A letter or
?must matchs[i - 1], and the rest must already match:dp[i - 1][j - 1]. - A
*that stops here matches the empty sequence:dp[i][j - 1]. - A
*that eats one more takess[i - 1]and stays available for earlier letters:dp[i - 1][j].
Case 3 is what lets one star cover any number of letters: each step up its column removes one more. Trying every length for every star by recursion repeats the same (i, j) pairs; the table solves each once. The same grid, with a star that repeats the previous character instead, solves Regular Expression Matching. Both are two-string dynamic programming like Edit Distance; for DP over ranges of one array, see Burst Balloons.
Interactive Walkthrough
The pattern runs across the top and the string down the left. Each cell shows T or F, and the cell its true came from is tinted: diagonal, left (empty star) or up (star eats a letter). Try Near miss to see a pattern that almost fits.
Dry Run Table
Input: s = "adceb" (down), p = "*a*b" (across)
| ∅ | * | 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 |
- Column 1: the first
*matches every prefix, so it is all T. - Column 3: the second
*starts at rowa(empty) and eatsd,c,e,bgoing down. - Bottom-right:
bmatches and the diagonaldp[4][3]is T.
Answer: true: the first * is empty, the second covers "dce".
The Solution Template
A bottom-up table that runs row 0 too, so leading stars match the empty string.
Wildcard Matching Code
1var isMatch = function(s, p) {2 const m = s.length, n = p.length;3 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));4 dp[0][0] = true;5 for (let i = 0; i <= m; i++) {6 for (let j = 1; j <= n; j++) {7 const c = p[j - 1];8 if (c === '*') {9 dp[i][j] = dp[i][j - 1] || (i > 0 && dp[i - 1][j]);10 } else {11 dp[i][j] = i > 0 && (c === '?' || c === s[i - 1]) && dp[i - 1][j - 1];12 }13 }14 }15 return dp[m][n];16};
Edge Cases & Common Mistakes
- Skipping row 0: a pattern of only stars matches the empty string; without row 0,
s = "a",p = "**a"returns false. - Mixing up with regex: here
*stands alone; its empty case isdp[i][j - 1], notdp[i][j - 2]. ?vs*:?matches exactly one letter, never zero.- Partial matches: the whole string must match, so
"a"does not match"aa". - Large C stack: with long inputs the C array
dp[m + 1][n + 1]can overflow the stack; allocate it on the heap or keep one row.
Summary
Set dp[0][0] = true and fill every row, including the empty string. A letter or ? reads the diagonal; a * reads one to the left (empty) or straight up (eats a letter). Return dp[m][n]. O(m · n) time, and O(n) space with one row.
More practice: DSA interview questions with answers · patterns cheat sheet