Skip to main content

44. Wildcard Matching

hardAsked at Airbnb

Match a string against a pattern with '?' (any single char) and '*' (any sequence including empty). Airbnb asks this to test 2D DP plus the greedy two-pointer optimization that beats it on space.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb senior+ onsite reports list this as a recurring DP hard.
  • Blind (2025-12)— Recurring in Airbnb L5 algorithm-track interviews.

Problem

Given an input string s and a pattern p, implement wildcard pattern matching with support for '?' and '*' where '?' matches any single character and '*' matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).

Constraints

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

Examples

Example 1

Input
s = "aa", p = "a"
Output
false

Example 2

Input
s = "aa", p = "*"
Output
true

Example 3

Input
s = "cb", p = "?a"
Output
false

Example 4

Input
s = "adceb", p = "*a*b"
Output
true

Approaches

1. Bottom-up DP table

dp[i][j] = true if s[0..i] matches p[0..j]. '*' is either 'empty' (carry dp[i][j-1]) or 'extend' (dp[i-1][j]).

Time
O(m * n)
Space
O(m * n)
function isMatch(s, p) {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= n; j++) if (p[j - 1] === '*') dp[0][j] = dp[0][j - 1];
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*') {
        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
      } else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}

Tradeoff: Classic 2D DP — easy to reason about, easy to verify against examples. The '*' recurrence captures both 'empty match' and 'extend one' in O(1).

2. DP with rolling 1D array

Same recurrence; only need the previous row to compute the next.

Time
O(m * n)
Space
O(n)
function isMatch1D(s, p) {
  const m = s.length, n = p.length;
  let prev = new Array(n + 1).fill(false);
  prev[0] = true;
  for (let j = 1; j <= n; j++) if (p[j - 1] === '*') prev[j] = prev[j - 1];
  for (let i = 1; i <= m; i++) {
    const cur = new Array(n + 1).fill(false);
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*') cur[j] = prev[j] || cur[j - 1];
      else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) cur[j] = prev[j - 1];
    }
    prev = cur;
  }
  return prev[n];
}

Tradeoff: Same asymptotic time, linear space. Worth mentioning if the interviewer asks about memory.

3. Greedy two-pointer with star backtracking

Walk both strings. On '?' or letter-match, advance both. On '*', remember the position and try to match nothing first. On mismatch, fall back to the last '*' and consume one more char.

Time
O(m * n) worst case, O(m + n) typical
Space
O(1)
function isMatchGreedy(s, p) {
  let i = 0, j = 0, starJ = -1, iMatched = 0;
  while (i < s.length) {
    if (j < p.length && (p[j] === '?' || p[j] === s[i])) { i++; j++; }
    else if (j < p.length && p[j] === '*') { starJ = j; iMatched = i; j++; }
    else if (starJ !== -1) { j = starJ + 1; iMatched++; i = iMatched; }
    else return false;
  }
  while (j < p.length && p[j] === '*') j++;
  return j === p.length;
}

Tradeoff: O(1) space, often much faster than DP on real inputs. Tradeoff: harder to reason about correctness — write it after the DP version cements the problem.

Airbnb-specific tips

Airbnb interviewers want both the DP and the greedy in your toolkit. Lead with the DP recurrence — that earns the bar. Then mention the greedy as the constant-space refinement, and only code it if the interviewer asks for a more efficient version. Don't write the greedy cold; the backtracking is easy to get wrong under pressure.

Common mistakes

  • Confusing '*' here with regex '*' (which means 'zero or more of preceding char') — wildcard '*' is 'any sequence'.
  • Forgetting the dp[0][j] initialization — patterns of all '*' match the empty string.
  • In the greedy version, advancing j twice on the '*' star track.

Follow-up questions

An interviewer at Airbnb may pivot to one of these next:

  • Regular Expression Matching (LC 10) — different '*' semantics, different DP.
  • Glob-style matching with character classes ('[abc]').
  • Compile a wildcard pattern to a faster runtime matcher.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

DP or greedy — which does Airbnb prefer?

Both work. DP is safer under interview pressure. Greedy is a 'I know one more thing' bonus if you've practiced it.

Why dp[0][j] for leading stars?

Pattern '*' matches the empty string. So dp[0][1] is true iff p[0] is '*'. The init loop propagates this for runs of leading stars.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Wildcard Matching and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →