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 Sam K., 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.

More Airbnb coding interview questions

See all Airbnb problems →

Companies that also ask Wildcard Matching