Skip to main content

96. Wildcard Matching

hardAsked at Reddit

Match a string against a pattern with '?' and '*'. Reddit uses this DP problem to test pattern-matching state — the same shape used in their AutoModerator regex-lite engine for subreddit-specific rules.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit content-platform hard question.

Problem

Given an input string s and a pattern p, implement wildcard pattern matching with support for '?' and '*' where: '?' 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 = "adceb", p = "*a*b*"
Output
true

Approaches

1. Recursion no memo

Branch on * (match zero or one+).

Time
exponential
Space
O(s + p)
// TLE without memoization.

Tradeoff: Exponential.

2. DP 2D bottom-up (optimal)

dp[i][j] = does s[0..i) match p[0..j). For *, dp[i][j] = dp[i-1][j] (consume) or dp[i][j-1] (skip).

Time
O(s * p)
Space
O(s * p)
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] === '?' || s[i-1] === p[j-1]) dp[i][j] = dp[i-1][j-1];
    }
  }
  return dp[m][n];
}

Tradeoff: Bottom-up DP — clean recurrence. Space can be reduced to O(p) with rolling rows.

Reddit-specific tips

Reddit interviewers want the DP. Bonus signal: explain the * recurrence verbally — 'consume the char (i-1 j) or skip the * (i j-1)'. Mention greedy O(s + p) as a faster alternative.

Common mistakes

  • Forgetting the base case for leading *s in pattern.
  • Confusing the s vs. p indices (off-by-one).
  • Treating * like regex (zero-or-more of preceding) — here * matches ANY sequence.

Follow-up questions

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

  • Regular expression matching (LC 10).
  • Edit distance (LC 72).
  • Longest common subsequence.

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 is the recurrence two options for *?

* can match the empty (dp[i][j-1] = pattern advances, no chars consumed) or one more char (dp[i-1][j] = consume one more s char, * stays).

Greedy solution?

Walk both with backtracking on *. O(s + p) average but harder to write cleanly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →