Skip to main content

89. Wildcard Matching

hardAsked at Plaid

Implement wildcard matching with '?' (single char) and '*' (any sequence). Plaid asks this because matching merchant patterns with arbitrary-length wildcards is part of their pattern-based category rules.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III hard pattern matching.
  • LeetCode Discuss (2026)— Plaid wildcard variant.

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

Approaches

1. 2D DP

dp[i][j] = does s[0..i] match p[0..j]? '?' matches any single; '*' matches empty or one more.

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 && p[j - 1] === '*'; j++) dp[0][j] = true;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
    }
  }
  return dp[m][n];
}

Tradeoff: Quadratic time and space.

2. Greedy with star backtracking

Walk both strings. On '*' remember last star and current position. On mismatch, jump back to last star + 1 in s.

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

Tradeoff: Constant space. The backtracking on '*' is the trick — record where you were and rewind to one char later if the rest fails.

Plaid-specific tips

Plaid grades this on whether you avoid the O(m*n) trap with the greedy approach. Bonus signal: trace the worst case ('aaaaab' vs 'a*a*a*b') to show that the greedy degenerates but in practice is fast. Connect to merchant-pattern compile-once, match-many.

Common mistakes

  • Forgetting that '*' can match the empty sequence — dp[i][j] = dp[i][j-1] OR dp[i-1][j].
  • Treating '*' the same as in regex '*' (preceding char) — wildcard '*' is its own token, independent.
  • Failing to consume trailing '*'s after the loop.

Follow-up questions

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

  • Regular expression matching (LC 10) — different '*' semantics.
  • Streaming match — bounded memory.
  • Compile pattern to a fast matcher with precomputation.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

How is wildcard '*' different from regex '*'?

Wildcard '*' matches any sequence of characters. Regex '*' matches zero or more of the preceding char.

Why greedy can degenerate?

Adversarial patterns like 'a*a*a*b' on 'aaaaab' force many rewinds. Each rewind shifts match by one, giving O(m*n) worst case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →