Skip to main content

90. Wildcard Matching

hardAsked at Snowflake

Implement wildcard pattern matching with ? and *. Snowflake asks this because LIKE patterns in their SQL engine are exactly this matching — % maps to *, _ maps to ?, and the engine must compile patterns efficiently.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake function-team uses this for LIKE/ILIKE implementation discussion.
  • LeetCode Discuss (2025-12)— Recurring at Snowflake SDE-II onsites.

Problem

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' matches any single character. '*' 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] = whether s[:i] matches p[:j]. Transitions on letter, ?, * (zero or 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; 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: Clean 2D DP.

2. Greedy with backtrack (optimal)

Walk s and p with cursors. On match or ?, advance both. On *, remember position; only advance p. On mismatch, restore to '* + 1 more s char' position. Linear in average.

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

Tradeoff: O(1) state. Fast in practice — only backtracks when a literal mismatch follows a *.

Snowflake-specific tips

Snowflake interviewers want both versions discussed, with trade-offs. Bonus signal: connect to LIKE pattern compilation — for patterns without %, Snowflake compiles to a simple substring search; with % the engine falls back to a DP or DFA matcher, identical to this problem.

Common mistakes

  • Mixing up * (zero or more anything) with regex's * (zero or more of previous) — they're different semantics.
  • Forgetting the trailing-* skip at the end of the greedy version.
  • Allocating a fresh array every iteration in DP — slow constants.

Follow-up questions

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

  • Regular Expression Matching (LC 10) — semantics differ.
  • How does Snowflake compile LIKE patterns?
  • Convert pattern to NFA/DFA.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why greedy plus backtrack?

Most matches don't need backtracking. When they do (a literal char fails after a *), we 'try matching one more char with *' — bounded backtracking.

How does this connect to LIKE?

Snowflake's LIKE uses similar pattern compilation. For simple patterns ('%abc') it does substring search; for complex patterns ('%a%b%c%'), it falls back to a DP matcher with the same recurrence.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →