Wildcard Matching

HardString DP · Greedy Backtracking🧩 String DP LeetCode #44 ↗Updated Oct 30, 2026

Problem

Decide whether pattern p matches the whole text s. In the pattern, ? stands for exactly one arbitrary character and * stands for any run of characters, including an empty one; every other character must match itself.

Inputs = "aa", p = "a"Outputfalse

Inputs = "aa", p = "*"Outputtrue

Inputs = "adceb", p = "*a*b"Outputtrue

0 ≤ s.length, p.length ≤ 2000 · s: lowercase letters · p: lowercase letters, ? or *

Try it yourself

Java

class Solution {
    public boolean isMatch(String s, String p) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A * has only two moves: match nothing (skip it) or swallow one more char and stay. That gives a clean 2-D DP — and because only the latest star ever needs to be revisited, a greedy two-pointer scan with one backtrack point solves it in O(1) space.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForceRecursion on (text index, pattern index)

Time O(2^m+n)Space O(m+n)

match(i, j): if the pattern is used up, the text must be too. A * either skips itself (j+1) or eats s[i] and stays (i+1). Otherwise the current chars must agree (or be ?) and both indices advance.

Java

public boolean isMatch(String s, String p) {
    return match(s, p, 0, 0);
}

private boolean match(String s, String p, int i, int j) {
    if (j == p.length()) return i == s.length();
    char c = p.charAt(j);
    if (c == '*') {
        // star matches empty, or absorbs s[i] and stays on the star
        return match(s, p, i, j + 1) || (i < s.length() && match(s, p, i + 1, j));
    }
    return i < s.length() && (c == '?' || c == s.charAt(i)) && match(s, p, i + 1, j + 1);
}

Directly encodes the rules, but patterns with many stars branch exponentially.

BetterBottom-Up 2-D DP Table

Time O(m·n)Space O(m·n)

dp[i][j] = does p[0..j) match s[0..i). An empty text only matches a pattern prefix made of stars. For a star, take dp[i][j-1] (star empty) or dp[i-1][j] (star eats s[i-1]); for anything else, take the diagonal if the chars agree.

Java

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char c = p.charAt(j - 1);
            if (c == '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (c == '?' || c == s.charAt(i - 1));
            }
        }
    }
    return dp[m][n];
}

Guaranteed O(m·n) and easy to prove, but stores 4 million cells at the limits.

OptimalGreedy Two Pointers with Star Backtrack

Time O(m·n) worstSpace O(1)

Walk s and p together. On a *, remember its position and the text index, and first let it match nothing. On a mismatch, go back to the last star and let it absorb one more char. Older stars never need revisiting: the last star can already cover anything an earlier one could.

Java

public boolean isMatch(String s, String p) {
    int i = 0, j = 0;
    int star = -1, mark = 0; // last '*' in p, and where its match in s begins
    while (i < s.length()) {
        if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            i++;
            j++;
        } else if (j < p.length() && p.charAt(j) == '*') {
            star = j;
            mark = i;
            j++; // try matching empty first
        } else if (star != -1) {
            j = star + 1;
            mark++; // let the star absorb one more char
            i = mark;
        } else {
            return false;
        }
    }
    while (j < p.length() && p.charAt(j) == '*') j++;
    return j == p.length();
}

Dry runs = "aa", p = "a"

i text indexm mark changed

j=0 '*'
a
i m
d

c

e

b

star=0, j=1
j=1 'a'
a
m
d
i
c

e

b

a==a, j=2
j=2 '*'
a

d
i m
c

e

b

star=2, j=3
j=3 'b'
a

d

c
i m
e

b

d≠b: star eats d
j=3 'b'
a

d

c

e

b
i m
star eats c, e
done
a

d

c

e

b
m
b==b, j=4=|p| ✔

Constant memory and near-linear on typical inputs — the best practical answer.

Pro tip

Collapse runs of ** into one star before running the DP — they are equivalent and it cuts the table width.

At a glance

Level	Approach	Time	Space
Brute Force	Recursion on (text index, pattern index)	`O(2^m+n)`	`O(m+n)`
Better	Bottom-Up 2-D DP Table	`O(m·n)`	`O(m·n)`
Optimal	Greedy Two Pointers with Star Backtrack	`O(m·n) worst`	`O(1)`

Common pitfalls

Forgetting trailing stars: s="ab", p="ab**" must still return true.
Initialising dp[0][j] as true for any pattern — only all-star prefixes match empty text.
Confusing this with regex * (Regular Expression Matching), where * repeats the previous char.

Interview tips

State the two choices for a star (empty vs. absorb one) before writing any code.
Present the DP first for correctness, then the greedy as an O(1)-space refinement.
Justify the greedy: only the most recent star needs backtracking.

Pattern

Pattern-vs-text DP → when wildcards create “skip or consume” choices on two strings.

My notes saved in this browser