How do you solve Wildcard Matching using the Bottom-Up — 2-D Table Over Prefixes (Optimal) approach?

When to use it: The answer they want. Frame it as 'dp[i][j] = does the first i chars of s match the first j chars of p', filled row by row. Let `dp[i][j]` be true when the first `i` characters of `s` match the first `j` characters of `p`. Initialise `dp[0][0] = true`, set the base row, then fill the grid row by row. The answer is `dp[n][m]`. **The base row is where most bugs live.** `dp[0][0] = true` (empty matches empty). For `dp[0][j]` (matching an empty `s` against a pattern prefix), the only way to succeed is if every pattern character so far is a star, each matching the empty string — so `dp[0][j] = dp[0][j-1]` when `p[j-1] == '*'`, and false otherwise. The first column `dp[i][0]` for `i > 0` is false: a non-empty string can't match an empty pattern. Skip the star handling in the base row and patterns like `"*a"` against `"a"` silently fail. **The transition mirrors the recursion.** For each `i, j ≥ 1`: - If `p[j-1]` is a literal equal to `s[i-1]`, or `'?'`, the characters align one-to-one: `dp[i][j] = dp[i-1][j-1]`. - If `p[j-1]` is `'*'`, it either matches one more character of `s` (`dp[i-1][j]`, star stays) or matches the empty string (`dp[i][j-1]`, star contributes nothing): `dp[i][j] = dp[i-1][j] || dp[i][j-1]`. - Otherwise (literal mismatch), `dp[i][j] = false`. **Why this order works.** `dp[i][j]` reads only cells above (`dp[i-1][*]`) and to the left in the same row (`dp[i][j-1]`). Iterating `i` outer (top to bottom) and `j` inner (left to right) guarantees every dependency is already computed — no recursion, no stack, so the Python recursion-limit problem disappears entirely. **Space compression.** Since row `i` depends only on row `i-1` and earlier cells of row `i`, keep just two rolling rows (or one row updated carefully) for `O(m)` space. **Why '*' here ≠ regex '*'.** This `'*'` is a standalone any-sequence token, so its transition combines 'consume a char' and 'consume nothing'. Regex `'*'` means 'zero or more of the *previous* element', which needs a different recurrence looking back at `p[j-2]`. State the contrast — interviewers probe whether you know the difference. Time complexity: O(n·m). Space complexity: O(m) with rolling rows.

Loading…

mediumDynamic ProgrammingLC #44Frequently asked

Wildcard Matching

Q: How do you solve Wildcard Matching using the Brute Force — Recursion with Star Branching approach?

When to use it: Say this first to establish the per-character cases and the two-way '*' branch, then flag the exponential blow-up from stars. Define `solve(i, j)` = does `s[i:]` match `p[j:]`? Handle the pattern character at `j`: - If `j` reached the end of `p`, the match succeeds only if `i` also reached the end of `s` (nothing left to consume). - If `p[j]` is `'*'`, branch: either it matches one more character of `s` (recurse `solve(i+1, j)`, the star stays available) or it matches the empty string (recurse `solve(i, j+1)`, step past the star). Return true if either works. - If `p[j]` is `'?'` or equals `s[i]` (and `i` is in range), it consumes one character on each side: recurse `solve(i+1, j+1)`. - Otherwise it's a literal mismatch → false. **The mental shift: '*' is the only source of choice.** Literals and `'?'` are forced moves — they either align one-to-one or fail immediately. All the branching, and all the difficulty, comes from `'*'`, which has to decide *how many* characters of `s` to absorb. Modeling that as 'absorb one more (`i+1`, star stays)' versus 'absorb none (`j+1`)' covers every possibility: repeatedly choosing 'one more' lets a single star swallow any length, and choosing 'none' ends it. **Why the two base cases.** Running out of pattern with characters of `s` left means failure (nothing to match them). Running out of `s` with pattern left is fine *only* if everything remaining is stars, each matching empty — and the star branch `solve(i, j+1)` naturally walks through exactly that. **Why we don't ship this.** Each star doubles the recursion, and the same `(i, j)` state is reached through many different star decisions — massive overlap. Caching `solve(i, j)` collapses it to `O(n·m)`. Time complexity: O(2^(n+m)). Space complexity: O(n + m).

Q: How do you solve Wildcard Matching using the Top-Down Memoization on (i, j) approach?

When to use it: The fix once you name the overlap — 'cache solve(i, j) so each pointer pair is computed once'. Keep the exact recurrence but cache `solve(i, j)`. Use a tri-state memo — unknown, true, or false — because the answer is a boolean and you can't use 'false' to mean 'not yet computed'. **The mental shift: the answer depends only on the two pointers.** Whatever sequence of star decisions brought you to `(i, j)`, the question 'does `s[i:]` match `p[j:]`?' has a fixed answer. Caching by `(i, j)` removes every duplicate subtree, and since there are only `O(n·m)` pointer pairs and each costs `O(1)` to combine, the total is `O(n·m)`. **Why the state is two indices.** The match position in `s` and the match position in `p` are independent, and both are needed — same shape as Edit Distance and LCS. The memo is naturally 2-D. **A language note (Java memo vs Python tabulation).** This recursion nests up to `O(n + m)` deep. With lengths up to 2000, that depth can reach ~4000 — comfortably fine in Java, but it **exceeds Python's default recursion limit of about 1000**. So in Python you'd either raise the limit with `sys.setrecursionlimit` or, better, switch to the bottom-up table (next approach), which uses no recursion stack at all. This is a concrete case where the same algorithm is cleanest top-down in Java but safest bottom-up in Python. Time complexity: O(n·m). Space complexity: O(n·m).

LCPractice

Dynamic Programming · 30 of 44 · 12 min

Given an input string s and a pattern p, implement wildcard matching that supports:

'?' — matches any single character.
'*' — matches any sequence of characters, including the empty sequence.

The match must cover the **entire** input string s (not a partial match). Return true if p matches s, otherwise false.

Here s contains only lowercase letters; p contains lowercase letters, '?', and '*'.

In plain English

Ask whether the first i characters of s can be produced by the first j characters of p. Each pattern character is one of three kinds: a literal (must equal the current s char), '?' (matches any single char), or '*' (a flexible token that can absorb zero or more characters of s). The answer to the whole problem is whether all of s is consumed by all of p, i.e. dp[n][m]. The only branching comes from '*', which can either grab another character of s or step aside as the empty match.

Examples

Example 1

Input: s = "aa", p = "a"
Output: false
Note: 'a' matches only the first character; there's no token to consume the second 'a'.

Example 2

Input: s = "adceb", p = "*a*b"
Output: true
Note: First '*' matches empty, 'a' matches 'a', second '*' matches 'dce', 'b' matches 'b'.

Example 3

Input: s = "acdcb", p = "a*c?b"
Output: false
Note: 'a' matches 'a', '*' can match 'cd', 'c' matches 'c', '?' matches 'b' — but then there's nothing left to match the final 'b'.

Constraints

0 ≤ s.length, p.length ≤ 2000
s contains only lowercase English letters
p contains lowercase letters, '?' and '*'
'*' matches any sequence including empty; '?' matches exactly one character

Clarifying questions4First question: Does '*' mean 'any sequence' or 'zero or more of the previous character'?Explore questions

Q1.Does '*' mean 'any sequence' or 'zero or more of the previous character'?
Any sequence (glob-style), including empty. It's NOT the regex meaning. That changes the '*' transition entirely — here '*' stands on its own.
Q2.Can '*' match the empty string?
Yes. A pattern like '*' matches '' and 'abc' alike. That's why dp[i][j-1] (star matches empty) is part of the transition and why a leading run of stars must match an empty s.
Q3.Must the pattern cover all of s?
Yes — it's a full match, not a search. The answer is dp[n][m], requiring all of s consumed by all of p.
Q4.What if s is empty?
Then p matches only if p is empty or consists entirely of stars. That's exactly what the dp[0][j] base row encodes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Match string s against a pattern p where '?' matches any single character and '*' matches any sequence (including empty). It's a 2-D grid DP: dp[i][j] is true if the first i characters of s match the first j characters of p. A normal char or '?' aligns one-to-one (dp[i][j] = dp[i-1][j-1]); a '*' either consumes one more character of s (dp[i-1][j]) or matches the empty string (dp[i][j-1]). O(n·m) time and space, reducible to O(m). The trap is the empty-prefix base case: a leading run of '*' must still match an empty s.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model it as a 2-D prefix-vs-prefix DP, get the two-way '*' transition right (match one more char OR match empty), and handle the empty-s base case where leading stars still match.

Where candidates slip

Treating '*' like regex '*' (zero-or-more of the previous char), botching the dp[0][j] base row so leading stars don't match an empty string, or forgetting that '*' can match the empty sequence.

How to stand out

State the recurrence cleanly: literal/'?' aligns one-to-one, '*' is dp[i-1][j] OR dp[i][j-1]. Nail the base row, then mention the O(m) rolling-array compression and contrast '*' here vs regex '*'.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion with Star Branching	`O(2^(n+m))`	`O(n + m)`	Say this first to establish the per-character cases and the two-way '*' branch, then flag the exponential blow-up from stars.	Read
2	Top-Down Memoization on (i, j)	`O(n·m)`	`O(n·m)`	The fix once you name the overlap — 'cache solve(i, j) so each pointer pair is computed once'.	Read
3	Bottom-Up — 2-D Table Over Prefixes (Optimal)Optimal	`O(n·m)`	`O(m) with rolling rows`	The answer they want. Frame it as 'dp[i][j] = does the first i chars of s match the first j chars of p', filled row by row.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMatch s against pattern with ? and *Does * mean any sequence?No, regex (prev char)Yes, globExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion with Star Branching

TimeO(2^(n+m))SpaceO(n + m)

Say this first to establish the per-character cases and the two-way '*' branch, then flag the exponential blow-up from stars.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk both strings with pointers i (into s) and j (into p). If the pattern char is a literal or '?', it must consume exactly one character of s. When does that succeed?

2Hint 2Explore hint

When you hit a '*', it has two choices: match the empty string and move past it (advance j), or match one more character of s (advance i, keep the '*'). Try both.

3Hint 3Explore hint

Base cases: if you run out of pattern, you match only if s is also exhausted; if you run out of s, the rest of the pattern must be all stars.

A · Core idea

Define solve(i, j) = does s[i:] match p[j:]? Handle the pattern character at j:

If j reached the end of p, the match succeeds only if i also reached the end of s (nothing left to consume).
If p[j] is '*', branch: either it matches one more character of s (recurse solve(i+1, j), the star stays available) or it matches the empty string (recurse solve(i, j+1), step past the star). Return true if either works.
If p[j] is '?' or equals s[i] (and i is in range), it consumes one character on each side: recurse solve(i+1, j+1).
Otherwise it's a literal mismatch → false.

The mental shift: '*' is the only source of choice. Literals and '?' are forced moves — they either align one-to-one or fail immediately. All the branching, and all the difficulty, comes from '*', which has to decide how many characters of s to absorb. Modeling that as 'absorb one more (i+1, star stays)' versus 'absorb none (j+1)' covers every possibility: repeatedly choosing 'one more' lets a single star swallow any length, and choosing 'none' ends it.

Why the two base cases. Running out of pattern with characters of s left means failure (nothing to match them). Running out of s with pattern left is fine only if everything remaining is stars, each matching empty — and the star branch solve(i, j+1) naturally walks through exactly that.

Why we don't ship this. Each star doubles the recursion, and the same (i, j) state is reached through many different star decisions — massive overlap. Caching solve(i, j) collapses it to O(n·m).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ab", p = "*b"

solve(0,0): p[0]='*'

try match-one → solve(1,0)

Statestar absorbs 'a'

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isMatch(String s, String p) { return solve(s, p, 0, 0); } // does s[i:] match p[j:] ?Explore the full code

solution.javaJava

Brute Force — Recursion with Star Branching — reference

4 teaching notes

1
public boolean isMatch(String s, String p) {
2
    return solve(s, p, 0, 0);
3
}
4
 
5
// does s[i:] match p[j:] ?
6
private boolean solve(String s, String p, int i, int j) {
7
    // Pattern exhausted — a match only if s is also fully consumed.
8
    if (j == p.length()) {
9
        return i == s.length();
10
    }
11
    if (p.charAt(j) == '*') {
12
        // match one more char of s (star stays) OR match empty (skip star)
13
        // Star matches one more char of s and stays available for more.
14
        if (i < s.length() && solve(s, p, i + 1, j)) {
15
            return true;
16
        }
17
        // Star matches the empty string and we move past it.
18
        return solve(s, p, i, j + 1);
19
    }
20
    // '?' or a literal match consumes exactly one char on each side.
21
    if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
22
        return solve(s, p, i + 1, j + 1);
23
    }
24
    return false;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(2^(n+m)) timeO(n + m) spaceOpen the invariant and proofExplore the proof

The state is the pair of pointers (i, j) into the two strings, and the recursion revisits the same (i, j) through different star choices. Two-pointer state plus exponential overlap is the textbook signal for an O(n·m) two-sequence DP.

ComplexityO(2^(n+m)) time, O(n + m) space — Each '*' forks into two recursive calls and those forks overlap heavily, so without caching the tree is exponential in n + m. Recursion depth is O(n + m).

E · Edge cases and pitfalls5s = "", p = "" — j and i both at end immediately → true.Explore edge cases

Edge cases handled

s = "", p = ""j and i both at end immediately → true.
s = "", p = "***"Each star takes the match-empty branch → true.

Pitfalls

Forgetting the star's match-empty branch — fails on patterns where '*' should match nothing.
Letting a literal/'?' consume a char without the i < length guard — index out of range.
Skipping this approach — verbalising the two-way star branch is what the interviewer grades.

03.2

Approach 2 of 3

Top-Down Memoization on (i, j)

TimeO(n·m)SpaceO(n·m)

The fix once you name the overlap — 'cache solve(i, j) so each pointer pair is computed once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

solve(i, j) returns the same boolean every call. Where can you store it so each (i, j) is computed once?

2Hint 2Explore hint

Use a 2-D memo of size (n+1) × (m+1) holding a tri-state: unknown / true / false. Check on entry, fill before returning.

3Hint 3Explore hint

There are O(n·m) states and each does O(1) work → O(n·m) time and space.

A · Core idea

Keep the exact recurrence but cache solve(i, j). Use a tri-state memo — unknown, true, or false — because the answer is a boolean and you can't use 'false' to mean 'not yet computed'.

The mental shift: the answer depends only on the two pointers. Whatever sequence of star decisions brought you to (i, j), the question 'does s[i:] match p[j:]?' has a fixed answer. Caching by (i, j) removes every duplicate subtree, and since there are only O(n·m) pointer pairs and each costs O(1) to combine, the total is O(n·m).

Why the state is two indices. The match position in s and the match position in p are independent, and both are needed — same shape as Edit Distance and LCS. The memo is naturally 2-D.

A language note (Java memo vs Python tabulation). This recursion nests up to O(n + m) deep. With lengths up to 2000, that depth can reach ~4000 — comfortably fine in Java, but it exceeds Python's default recursion limit of about 1000. So in Python you'd either raise the limit with sys.setrecursionlimit or, better, switch to the bottom-up table (next approach), which uses no recursion stack at all. This is a concrete case where the same algorithm is cleanest top-down in Java but safest bottom-up in Python.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "adceb", p = "*a*b"

solve(0,0) '*'

explores absorbing a prefix of s

Statememoized as it unwinds

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isMatch(String s, String p) { int n = s.length(), m = p.length(); Boolean[][] memo = new Boolean[n + 1][m + 1]; return solve(s, p, 0, 0, memo); }Explore the full code

solution.javaJava

Top-Down Memoization on (i, j) — reference

3 teaching notes

1
public boolean isMatch(String s, String p) {
2
    int n = s.length(), m = p.length();
3
    // Tri-state cache: null = unknown, true / false = computed. Can't use false as
4
    // 'empty'.
5
    Boolean[][] memo = new Boolean[n + 1][m + 1];
6
    return solve(s, p, 0, 0, memo);
7
}
8
 
9
private boolean solve(String s, String p, int i, int j, Boolean[][] memo) {
10
    if (j == p.length()) {
11
        return i == s.length();
12
    }
13
    // Cache hit returns the stored answer in O(1).
14
    if (memo[i][j] != null) {
15
        return memo[i][j];
16
    }
17
    boolean ans;
18
    if (p.charAt(j) == '*') {
19
        ans = (i < s.length() && solve(s, p, i + 1, j, memo))
20
              || solve(s, p, i, j + 1, memo);
21
    } else if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
22
        ans = solve(s, p, i + 1, j + 1, memo);
23
    } else {
24
        ans = false;
25
    }
26
    memo[i][j] = ans;
27
    return ans;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n·m) timeO(n·m) spaceOpen the invariant and proofExplore the proof

Standard DP upgrade: a correct recurrence plus a cache keyed on the true state (i, j), with a tri-state sentinel because the values are booleans. The intellectual work — the two-way star branch — was done in the brute force.

ComplexityO(n·m) time, O(n·m) space — There are (n+1)·(m+1) distinct (i, j) states; each resolves in O(1) given its sub-results → O(n·m) time. The memo is O(n·m); recursion depth is O(n + m) on top.

E · Edge cases and pitfalls5long s and p (~2000 each) — Java memo is fine; Python needs a raised recursion limit or the tabulation below.Explore edge cases

Edge cases handled

long s and p (~2000 each)Java memo is fine; Python needs a raised recursion limit or the tabulation below.
p = "*"Matches any s — the star's match-one branch walks all of s, then match-empty closes it.

Pitfalls

Using a primitive boolean memo where false doubles as 'uncomputed' — use Boolean/null or a separate visited flag.
Recursing in Python without raising the limit — n + m depth overflows the stack on long inputs.
Caching only on i or only on j — both pointers define the state.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — 2-D Table Over Prefixes (Optimal)

TimeO(n·m)SpaceO(m) with rolling rows

The answer they want. Frame it as 'dp[i][j] = does the first i chars of s match the first j chars of p', filled row by row.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp[i][j] mean: do the first i characters of s match the first j characters of p? dp[0][0] is true.

2Hint 2Explore hint

Build the base row dp[0][j]: empty s matches a pattern prefix only if it is all stars, so dp[0][j] = dp[0][j-1] when p[j-1]=='*'.

3Hint 3Explore hint

Transition: literal/'?' → dp[i-1][j-1]; '*' → dp[i-1][j] (match one more char) OR dp[i][j-1] (match empty). Answer dp[n][m].

A · Core idea

Let dp[i][j] be true when the first i characters of s match the first j characters of p. Initialise dp[0][0] = true, set the base row, then fill the grid row by row. The answer is dp[n][m].

The base row is where most bugs live. dp[0][0] = true (empty matches empty). For dp[0][j] (matching an empty s against a pattern prefix), the only way to succeed is if every pattern character so far is a star, each matching the empty string — so dp[0][j] = dp[0][j-1] when p[j-1] == '*', and false otherwise. The first column dp[i][0] for i > 0 is false: a non-empty string can't match an empty pattern. Skip the star handling in the base row and patterns like "*a" against "a" silently fail.

The transition mirrors the recursion. For each i, j ≥ 1:

If p[j-1] is a literal equal to s[i-1], or '?', the characters align one-to-one: dp[i][j] = dp[i-1][j-1].
If p[j-1] is '*', it either matches one more character of s (dp[i-1][j], star stays) or matches the empty string (dp[i][j-1], star contributes nothing): dp[i][j] = dp[i-1][j] || dp[i][j-1].
Otherwise (literal mismatch), dp[i][j] = false.

Why this order works. dp[i][j] reads only cells above (dp[i-1][*]) and to the left in the same row (dp[i][j-1]). Iterating i outer (top to bottom) and j inner (left to right) guarantees every dependency is already computed — no recursion, no stack, so the Python recursion-limit problem disappears entirely.

Space compression. Since row i depends only on row i-1 and earlier cells of row i, keep just two rolling rows (or one row updated carefully) for O(m) space.

Why '*' here ≠ regex '*'. This '*' is a standalone any-sequence token, so its transition combines 'consume a char' and 'consume nothing'. Regex '*' means 'zero or more of the previous element', which needs a different recurrence looking back at p[j-2]. State the contrast — interviewers probe whether you know the difference.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ab", p = "*b"

Interactive diagram

Cell dependencies in the prefix grid

dp[0][0]

Active call / nodeSupporting contextReturned stateNot active

dp[i][j] reads up-left (align), or for '*' it reads up (match one) and left (match empty). Iterate rows top-down, columns left-right.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Bottom-Up — 2-D Table Over Prefixes (Optimal) — optimal

4 teaching notes

1
public boolean isMatch(String s, String p) {
2
    int n = s.length(), m = p.length();
3
    boolean[][] dp = new boolean[n + 1][m + 1];
4
    dp[0][0] = true;
5
    for (int j = 1; j <= m; j++) {
6
        if (p.charAt(j - 1) == '*') {
7
            // The base-row star handling — the cell most people get wrong.
8
            dp[0][j] = dp[0][j - 1];   // leading stars match empty s
9
        }
10
    }
11
    for (int i = 1; i <= n; i++) {
12
        for (int j = 1; j <= m; j++) {
13
            char pc = p.charAt(j - 1);
14
            if (pc == '?' || pc == s.charAt(i - 1)) {
15
                // Literal or '?' aligns one character on each side.
16
                dp[i][j] = dp[i - 1][j - 1];
17
            } else if (pc == '*') {
18
                // Star: match one more char of s (up) OR match empty (left).
19
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
20
            }
21
        }
22
    }
23
    // Full match: all of s consumed by all of p.
24
    return dp[n][m];
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n·m) timeO(m) with rolling rows spaceOpen the invariant and proofExplore the proof

This is the canonical two-sequence prefix DP: state = (prefix of s, prefix of p), transition = align-one for literal/'?', branch for '*'. The same grid skeleton solves Edit Distance, LCS, and Regular Expression Matching — only the per-cell rule changes. Bottom-up also sidesteps Python's recursion limit.

ComplexityO(n·m) time, O(m) with rolling rows space — Filling an (n+1)·(m+1) table with O(1) work per cell is O(n·m) time. Each row depends only on the previous, so two rolling rows give O(m) space.

E · Edge cases and pitfalls6s = "", p = "" — dp[0][0] = true returned directly.Explore edge cases

Edge cases handled

s = "", p = ""dp[0][0] = true returned directly.
s = "", p = "*****"Base row propagates true across all stars → dp[0][m] true.
p has no wildcardsOnly the align-one branch fires — reduces to plain string equality.

Pitfalls

Forgetting the base-row star handling — patterns with leading '*' fail against an empty or short s.
Writing the '*' transition as dp[i-1][j-1] — that's the '?'/literal rule; '*' must use up OR left.
Compressing to one row but overwriting dp[i][j-1] before it's read — keep two rows or update carefully.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isMatch(String s, String p) { int n = s.length(), m = p.length(); boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true; for (int j = 1; j <= m; j++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Confusing wildcard '*' with regex '*'

Here '*' stands alone and matches any sequence, so its transition is dp[i-1][j] OR dp[i][j-1]. Regex '*' means 'zero or more of p[j-2]' and needs an entirely different recurrence. Mixing them up produces wrong answers on patterns like "a*".

Explore the code comparison

Don't write this

elif pc == '*':
    # WRONG: regex-style, looks at the previous pattern char
    dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and matches(p[j - 2], s[i - 1]))

Write this instead

elif pc == '*':
    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]   # match one more OR match empty

Base row ignores leading stars

If dp[0][j] is left false for star prefixes, a pattern like "*a" can never line up its star with an empty s, so "*abc" vs "abc" wrongly fails. Leading stars must match the empty string.

Explore the code comparison

Don't write this

dp[0][0] = true;
// (nothing else) — dp[0][j] stays false even for stars

Write this instead

dp[0][0] = true;
for (int j = 1; j <= m; j++) {
    if (p.charAt(j - 1) == '*') {
        dp[0][j] = dp[0][j - 1];
    }
}

Wrong '*' transition

Using the align-one rule for '*' forces it to consume exactly one character, so it can neither match empty nor absorb multiple characters. The star must combine 'up' (one more) and 'left' (empty).

Explore the code comparison

Don't write this

if (pc == '*') {
    dp[i][j] = dp[i - 1][j - 1];   // treats * like a single char
}

Write this instead

if (pc == '*') {
    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

2-D grid DP over (prefix of s, prefix of p); '*' branches into match-one vs match-empty

Code pattern to memorize

dp[0][0] = true
dp[0][j] = dp[0][j-1] if p[j-1]=='*'   (stars match empty)
if p[j-1]=='?' or p[j-1]==s[i-1]: dp[i][j] = dp[i-1][j-1]
elif p[j-1]=='*':                  dp[i][j] = dp[i-1][j] OR dp[i][j-1]
else:                              dp[i][j] = false
answer = dp[n][m]

Rules to remember

1'*' has two moves: match one more character of s (dp[i-1][j], star stays) or match the empty string and move past it (dp[i][j-1]).
2'?' and a literal match consume exactly one character each from s and p: dp[i][j] = dp[i-1][j-1].
3Base case dp[i][0] = false for i > 0 (empty pattern can't match non-empty s), but dp[0][j] can be true if p[0..j) is all stars.
4Don't confuse this with regex matching: here '*' stands alone (any sequence), it is not 'zero or more of the previous character'.
5The whole DP is monotone in one direction, so you can compress to a single rolling row → O(m) space.

Use this pattern when

Match a string against a pattern with single-char and multi-char wildcards
Two-sequence alignment where one side has 'match-any' tokens
Glob-style filename / path matching
Any problem reducible to 'does prefix of A align with prefix of B' with flexible tokens

Choose another pattern when

'*' means 'zero or more of the preceding element' → that's Regular Expression Matching, a different transition
You need the actual alignment, not just yes/no → reconstruct from the table, still DP
Pattern has no wildcards → plain string equality, no DP needed
You want all matching substrings in a text → Aho–Corasick / suffix automaton, not this DP

Interview takeaway

Wildcard Matching is the canonical two-prefix grid DP. The only subtlety is the '*' branch — match-one (consume a char, star stays) OR match-empty (skip the star) — and the empty-string base case where a leading run of stars must still match. Get those right and it's the same dp[i][j] = dp[i-1][j-1] alignment skeleton as Edit Distance and LCS.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical two-sequence prefix DP. Recognise it whenever you ask 'does a prefix of A align with a prefix of B' with flexible match tokens: literals/'?' align one-to-one, '*' branches into match-one (up) OR match-empty (left). Same grid as Edit Distance and LCS; bottom-up also avoids Python's recursion-depth limit on long inputs.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Regular Expression Matching
Coming soon
'*' means zero-or-more of the previous element and '.' is the single-char wildcard — a different, trickier transition.
Edit Distance
Same two-prefix grid DP; cells track minimum edits instead of a boolean match.
Longest Common Subsequence
The align-one-vs-skip grid skeleton, optimising a length rather than matching.
Wildcard Matching with O(1) Greedy Backtrack
Coming soon
A two-pointer greedy that remembers the last '*' position matches in O(n·m) worst case but O(1) space — worth mentioning as a follow-up.

Same pattern

←

Longest Palindromic Subsequence

Continue · Next problem

Abbreviation

mediumDynamic ProgrammingLC #44Frequently asked

Wildcard Matching

LCPractice

Dynamic Programming · 30 of 44 · 12 min

Given an input string s and a pattern p, implement wildcard matching that supports:

'?' — matches any single character.
'*' — matches any sequence of characters, including the empty sequence.

The match must cover the **entire** input string s (not a partial match). Return true if p matches s, otherwise false.

Here s contains only lowercase letters; p contains lowercase letters, '?', and '*'.

In plain English

Examples

Example 1

Input: s = "aa", p = "a"
Output: false
Note: 'a' matches only the first character; there's no token to consume the second 'a'.

Example 2

Input: s = "adceb", p = "*a*b"
Output: true
Note: First '*' matches empty, 'a' matches 'a', second '*' matches 'dce', 'b' matches 'b'.

Example 3

Input: s = "acdcb", p = "a*c?b"
Output: false
Note: 'a' matches 'a', '*' can match 'cd', 'c' matches 'c', '?' matches 'b' — but then there's nothing left to match the final 'b'.

Constraints

0 ≤ s.length, p.length ≤ 2000
s contains only lowercase English letters
p contains lowercase letters, '?' and '*'
'*' matches any sequence including empty; '?' matches exactly one character

Clarifying questions4First question: Does '*' mean 'any sequence' or 'zero or more of the previous character'?Explore questions

Q1.Does '*' mean 'any sequence' or 'zero or more of the previous character'?
Any sequence (glob-style), including empty. It's NOT the regex meaning. That changes the '*' transition entirely — here '*' stands on its own.
Q2.Can '*' match the empty string?
Yes. A pattern like '*' matches '' and 'abc' alike. That's why dp[i][j-1] (star matches empty) is part of the transition and why a leading run of stars must match an empty s.
Q3.Must the pattern cover all of s?
Yes — it's a full match, not a search. The answer is dp[n][m], requiring all of s consumed by all of p.
Q4.What if s is empty?
Then p matches only if p is empty or consists entirely of stars. That's exactly what the dp[0][j] base row encodes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model it as a 2-D prefix-vs-prefix DP, get the two-way '*' transition right (match one more char OR match empty), and handle the empty-s base case where leading stars still match.

Where candidates slip

Treating '*' like regex '*' (zero-or-more of the previous char), botching the dp[0][j] base row so leading stars don't match an empty string, or forgetting that '*' can match the empty sequence.

How to stand out

State the recurrence cleanly: literal/'?' aligns one-to-one, '*' is dp[i-1][j] OR dp[i][j-1]. Nail the base row, then mention the O(m) rolling-array compression and contrast '*' here vs regex '*'.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion with Star Branching	`O(2^(n+m))`	`O(n + m)`	Say this first to establish the per-character cases and the two-way '*' branch, then flag the exponential blow-up from stars.	Read
2	Top-Down Memoization on (i, j)	`O(n·m)`	`O(n·m)`	The fix once you name the overlap — 'cache solve(i, j) so each pointer pair is computed once'.	Read
3	Bottom-Up — 2-D Table Over Prefixes (Optimal)Optimal	`O(n·m)`	`O(m) with rolling rows`	The answer they want. Frame it as 'dp[i][j] = does the first i chars of s match the first j chars of p', filled row by row.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion with Star Branching

TimeO(2^(n+m))SpaceO(n + m)

Say this first to establish the per-character cases and the two-way '*' branch, then flag the exponential blow-up from stars.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk both strings with pointers i (into s) and j (into p). If the pattern char is a literal or '?', it must consume exactly one character of s. When does that succeed?

2Hint 2Explore hint

When you hit a '*', it has two choices: match the empty string and move past it (advance j), or match one more character of s (advance i, keep the '*'). Try both.

3Hint 3Explore hint

Base cases: if you run out of pattern, you match only if s is also exhausted; if you run out of s, the rest of the pattern must be all stars.

A · Core idea

Define solve(i, j) = does s[i:] match p[j:]? Handle the pattern character at j:

If j reached the end of p, the match succeeds only if i also reached the end of s (nothing left to consume).
If p[j] is '*', branch: either it matches one more character of s (recurse solve(i+1, j), the star stays available) or it matches the empty string (recurse solve(i, j+1), step past the star). Return true if either works.
If p[j] is '?' or equals s[i] (and i is in range), it consumes one character on each side: recurse solve(i+1, j+1).
Otherwise it's a literal mismatch → false.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ab", p = "*b"

solve(0,0): p[0]='*'

try match-one → solve(1,0)

Statestar absorbs 'a'

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isMatch(String s, String p) { return solve(s, p, 0, 0); } // does s[i:] match p[j:] ?Explore the full code

solution.javaJava

Brute Force — Recursion with Star Branching — reference

4 teaching notes

1
public boolean isMatch(String s, String p) {
2
    return solve(s, p, 0, 0);
3
}
4
 
5
// does s[i:] match p[j:] ?
6
private boolean solve(String s, String p, int i, int j) {
7
    // Pattern exhausted — a match only if s is also fully consumed.
8
    if (j == p.length()) {
9
        return i == s.length();
10
    }
11
    if (p.charAt(j) == '*') {
12
        // match one more char of s (star stays) OR match empty (skip star)
13
        // Star matches one more char of s and stays available for more.
14
        if (i < s.length() && solve(s, p, i + 1, j)) {
15
            return true;
16
        }
17
        // Star matches the empty string and we move past it.
18
        return solve(s, p, i, j + 1);
19
    }
20
    // '?' or a literal match consumes exactly one char on each side.
21
    if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
22
        return solve(s, p, i + 1, j + 1);
23
    }
24
    return false;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(2^(n+m)) timeO(n + m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5s = "", p = "" — j and i both at end immediately → true.Explore edge cases

Edge cases handled

s = "", p = ""j and i both at end immediately → true.
s = "", p = "***"Each star takes the match-empty branch → true.

Pitfalls

Forgetting the star's match-empty branch — fails on patterns where '*' should match nothing.
Letting a literal/'?' consume a char without the i < length guard — index out of range.
Skipping this approach — verbalising the two-way star branch is what the interviewer grades.

03.2

Approach 2 of 3

Top-Down Memoization on (i, j)

TimeO(n·m)SpaceO(n·m)

The fix once you name the overlap — 'cache solve(i, j) so each pointer pair is computed once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

solve(i, j) returns the same boolean every call. Where can you store it so each (i, j) is computed once?

2Hint 2Explore hint

Use a 2-D memo of size (n+1) × (m+1) holding a tri-state: unknown / true / false. Check on entry, fill before returning.

3Hint 3Explore hint

There are O(n·m) states and each does O(1) work → O(n·m) time and space.

A · Core idea

Keep the exact recurrence but cache solve(i, j). Use a tri-state memo — unknown, true, or false — because the answer is a boolean and you can't use 'false' to mean 'not yet computed'.

Why the state is two indices. The match position in s and the match position in p are independent, and both are needed — same shape as Edit Distance and LCS. The memo is naturally 2-D.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "adceb", p = "*a*b"

solve(0,0) '*'

explores absorbing a prefix of s

Statememoized as it unwinds

Final resulttrue

C · Code with teaching comments

solution.javaJava

Top-Down Memoization on (i, j) — reference

3 teaching notes

1
public boolean isMatch(String s, String p) {
2
    int n = s.length(), m = p.length();
3
    // Tri-state cache: null = unknown, true / false = computed. Can't use false as
4
    // 'empty'.
5
    Boolean[][] memo = new Boolean[n + 1][m + 1];
6
    return solve(s, p, 0, 0, memo);
7
}
8
 
9
private boolean solve(String s, String p, int i, int j, Boolean[][] memo) {
10
    if (j == p.length()) {
11
        return i == s.length();
12
    }
13
    // Cache hit returns the stored answer in O(1).
14
    if (memo[i][j] != null) {
15
        return memo[i][j];
16
    }
17
    boolean ans;
18
    if (p.charAt(j) == '*') {
19
        ans = (i < s.length() && solve(s, p, i + 1, j, memo))
20
              || solve(s, p, i, j + 1, memo);
21
    } else if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
22
        ans = solve(s, p, i + 1, j + 1, memo);
23
    } else {
24
        ans = false;
25
    }
26
    memo[i][j] = ans;
27
    return ans;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n·m) timeO(n·m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5long s and p (~2000 each) — Java memo is fine; Python needs a raised recursion limit or the tabulation below.Explore edge cases

Edge cases handled

long s and p (~2000 each)Java memo is fine; Python needs a raised recursion limit or the tabulation below.
p = "*"Matches any s — the star's match-one branch walks all of s, then match-empty closes it.

Pitfalls

Using a primitive boolean memo where false doubles as 'uncomputed' — use Boolean/null or a separate visited flag.
Recursing in Python without raising the limit — n + m depth overflows the stack on long inputs.
Caching only on i or only on j — both pointers define the state.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — 2-D Table Over Prefixes (Optimal)

TimeO(n·m)SpaceO(m) with rolling rows

The answer they want. Frame it as 'dp[i][j] = does the first i chars of s match the first j chars of p', filled row by row.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp[i][j] mean: do the first i characters of s match the first j characters of p? dp[0][0] is true.

2Hint 2Explore hint

Build the base row dp[0][j]: empty s matches a pattern prefix only if it is all stars, so dp[0][j] = dp[0][j-1] when p[j-1]=='*'.

3Hint 3Explore hint

Transition: literal/'?' → dp[i-1][j-1]; '*' → dp[i-1][j] (match one more char) OR dp[i][j-1] (match empty). Answer dp[n][m].

A · Core idea

The transition mirrors the recursion. For each i, j ≥ 1:

If p[j-1] is a literal equal to s[i-1], or '?', the characters align one-to-one: dp[i][j] = dp[i-1][j-1].
If p[j-1] is '*', it either matches one more character of s (dp[i-1][j], star stays) or matches the empty string (dp[i][j-1], star contributes nothing): dp[i][j] = dp[i-1][j] || dp[i][j-1].
Otherwise (literal mismatch), dp[i][j] = false.

Space compression. Since row i depends only on row i-1 and earlier cells of row i, keep just two rolling rows (or one row updated carefully) for O(m) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "ab", p = "*b"

Interactive diagram

Cell dependencies in the prefix grid

dp[0][0]

Active call / nodeSupporting contextReturned stateNot active

dp[i][j] reads up-left (align), or for '*' it reads up (match one) and left (match empty). Iterate rows top-down, columns left-right.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Bottom-Up — 2-D Table Over Prefixes (Optimal) — optimal

4 teaching notes

1
public boolean isMatch(String s, String p) {
2
    int n = s.length(), m = p.length();
3
    boolean[][] dp = new boolean[n + 1][m + 1];
4
    dp[0][0] = true;
5
    for (int j = 1; j <= m; j++) {
6
        if (p.charAt(j - 1) == '*') {
7
            // The base-row star handling — the cell most people get wrong.
8
            dp[0][j] = dp[0][j - 1];   // leading stars match empty s
9
        }
10
    }
11
    for (int i = 1; i <= n; i++) {
12
        for (int j = 1; j <= m; j++) {
13
            char pc = p.charAt(j - 1);
14
            if (pc == '?' || pc == s.charAt(i - 1)) {
15
                // Literal or '?' aligns one character on each side.
16
                dp[i][j] = dp[i - 1][j - 1];
17
            } else if (pc == '*') {
18
                // Star: match one more char of s (up) OR match empty (left).
19
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
20
            }
21
        }
22
    }
23
    // Full match: all of s consumed by all of p.
24
    return dp[n][m];
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n·m) timeO(m) with rolling rows spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s = "", p = "" — dp[0][0] = true returned directly.Explore edge cases

Edge cases handled

s = "", p = ""dp[0][0] = true returned directly.
s = "", p = "*****"Base row propagates true across all stars → dp[0][m] true.
p has no wildcardsOnly the align-one branch fires — reduces to plain string equality.

Pitfalls

Forgetting the base-row star handling — patterns with leading '*' fail against an empty or short s.
Writing the '*' transition as dp[i-1][j-1] — that's the '?'/literal rule; '*' must use up OR left.
Compressing to one row but overwriting dp[i][j-1] before it's read — keep two rows or update carefully.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Confusing wildcard '*' with regex '*'

Explore the code comparison

Don't write this

elif pc == '*':
    # WRONG: regex-style, looks at the previous pattern char
    dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and matches(p[j - 2], s[i - 1]))

Write this instead

elif pc == '*':
    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]   # match one more OR match empty

Base row ignores leading stars

If dp[0][j] is left false for star prefixes, a pattern like "*a" can never line up its star with an empty s, so "*abc" vs "abc" wrongly fails. Leading stars must match the empty string.

Explore the code comparison

Don't write this

dp[0][0] = true;
// (nothing else) — dp[0][j] stays false even for stars

Write this instead

dp[0][0] = true;
for (int j = 1; j <= m; j++) {
    if (p.charAt(j - 1) == '*') {
        dp[0][j] = dp[0][j - 1];
    }
}

Wrong '*' transition

Using the align-one rule for '*' forces it to consume exactly one character, so it can neither match empty nor absorb multiple characters. The star must combine 'up' (one more) and 'left' (empty).

Explore the code comparison

Don't write this

if (pc == '*') {
    dp[i][j] = dp[i - 1][j - 1];   // treats * like a single char
}

Write this instead

if (pc == '*') {
    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

2-D grid DP over (prefix of s, prefix of p); '*' branches into match-one vs match-empty

Code pattern to memorize

dp[0][0] = true
dp[0][j] = dp[0][j-1] if p[j-1]=='*'   (stars match empty)
if p[j-1]=='?' or p[j-1]==s[i-1]: dp[i][j] = dp[i-1][j-1]
elif p[j-1]=='*':                  dp[i][j] = dp[i-1][j] OR dp[i][j-1]
else:                              dp[i][j] = false
answer = dp[n][m]

Rules to remember

1'*' has two moves: match one more character of s (dp[i-1][j], star stays) or match the empty string and move past it (dp[i][j-1]).
2'?' and a literal match consume exactly one character each from s and p: dp[i][j] = dp[i-1][j-1].
3Base case dp[i][0] = false for i > 0 (empty pattern can't match non-empty s), but dp[0][j] can be true if p[0..j) is all stars.
4Don't confuse this with regex matching: here '*' stands alone (any sequence), it is not 'zero or more of the previous character'.
5The whole DP is monotone in one direction, so you can compress to a single rolling row → O(m) space.

Use this pattern when

Match a string against a pattern with single-char and multi-char wildcards
Two-sequence alignment where one side has 'match-any' tokens
Glob-style filename / path matching
Any problem reducible to 'does prefix of A align with prefix of B' with flexible tokens

Choose another pattern when

'*' means 'zero or more of the preceding element' → that's Regular Expression Matching, a different transition
You need the actual alignment, not just yes/no → reconstruct from the table, still DP
Pattern has no wildcards → plain string equality, no DP needed
You want all matching substrings in a text → Aho–Corasick / suffix automaton, not this DP

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Regular Expression Matching
Coming soon
'*' means zero-or-more of the previous element and '.' is the single-char wildcard — a different, trickier transition.
Edit Distance
Same two-prefix grid DP; cells track minimum edits instead of a boolean match.
Longest Common Subsequence
The align-one-vs-skip grid skeleton, optimising a length rather than matching.
Wildcard Matching with O(1) Greedy Backtrack
Coming soon
A two-pointer greedy that remembers the last '*' position matches in O(n·m) worst case but O(1) space — worth mentioning as a follow-up.

Same pattern

←

Longest Palindromic Subsequence

Continue · Next problem

Abbreviation