Wildcard Matching

Hard25–30 min

Topics

Dynamic ProgrammingString

Companies

GoogleFacebookAmazon

A pattern built from ordinary letters, single-character wildcards (?), and multi-character wildcards (*) is checked against a target string — the question is whether the pattern can be stretched or squeezed to cover the string entirely, not just a piece of it. Letters and ? are easy: they simply have to line up one-to-one. The * is what makes this genuinely tricky, since it isn't pinned to any particular number of characters, so a naive check has to be willing to try every length it could possibly absorb. The way through is to stop asking "how many characters does this * eat" up front, and instead ask a simpler yes/no question at every (position in s, position in p) pair: can the pattern up to here match the string up to here? A * then has just two ways to answer yes — either it isn't needed at all here (check without it), or it's already covering the last character of s and the same question just shifts one character earlier in s. Chaining that logic across the whole grid answers the original question without ever guessing a length.

Test Case 1:

Input:s = "aa", p = "a"

Output:false

Explanation:p has no wildcard at all, so it must match letter-for-letter — "a" is one character short of "aa".

Test Case 2:

Input:s = "aa", p = "*"

Output:true

Explanation:A lone '*' can stretch to absorb any number of characters, including both a's here.

Test Case 3:

Input:s = "", p = "?"

Output:false

Explanation:'?' insists on exactly one character being present — there's nothing for it to match against an empty s.

Constraints

◆0 ≤ s.length ≤ 10
◆0 ≤ p.length ≤ 10
◆s consists of lowercase English letters only
◆p consists of lowercase English letters, '?', and '*'

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

At each position, if the pattern character is '*', it can either vanish — matching zero characters and letting the rest of the pattern take over from the same spot in s — or eat one character of s and stick around to decide again next time. Trying both keeps every possibility on the table. A literal letter or '?' can only step forward together with s, one character at a time, and only if they actually agree. The catch is that the same (position in s, position in p) pair gets asked about repeatedly through completely different chains of '*' decisions, so the work balloons fast.

TimeO(2ⁿ⁺ᵐ)

SpaceO(n+m)

Java

Try it out

class Solution {
    private String s, p;
    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        return solve(0, 0);
    }
    private boolean solve(int i, int j) {
        if (j == p.length()) return i == s.length();
        boolean firstMatch = i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i));
        if (p.charAt(j) == '*') {
            return solve(i, j + 1) || (i < s.length() && solve(i + 1, j));
        }
        return firstMatch && solve(i + 1, j + 1);
    }
}

Optimal — Bottom-Up DP

Optimal

Track, for every prefix of s and every prefix of p, whether that prefix of p can fully cover that prefix of s. A literal or '?' just inherits the answer from one character back on both sides. A '*' is more generous — it inherits the answer either from leaving it out entirely (one column back, same row) or from having already used it to soak up the current character of s (same column, one row back); either path succeeding is enough. The very first row needs its own pass beforehand, since only a run of pure '*'s can ever match an empty s.

TimeO(n*m)

SpaceO(n*m)