Skip to main content

100. Wildcard Matching

hardAsked at Workday

Match a string against a pattern with '?' (single char) and '*' (any sequence). Workday uses this directly for RBAC pattern matching — same shape as evaluating policies like 'admin:*:write' against role strings.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday RBAC team — direct wildcard-policy analogy.

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. Recursive without memo

Try each pattern element; '*' branches into 'match empty' or 'consume one s char and stay'.

Time
O(exponential)
Space
O(s+p)
// without memo this blows up on stars

Tradeoff: Too slow.

2. 2D DP

dp[i][j] = s[..i] matches p[..j]. '*' either matches empty (dp[i][j-1]) or consumes one char (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: Standard 2D DP. The '*' case is the OR of 'consume one s char' (dp[i-1][j]) and 'match empty' (dp[i][j-1]).

Workday-specific tips

Workday wants the DP. Articulate the '*' branching: either match zero (dp[i][j-1]) or consume one s char and keep the star alive (dp[i-1][j]). This is different from LC 10's '*' meaning. Initialize dp[0][j] correctly: '*' at any prefix can match empty s.

Common mistakes

  • Treating LC 44 '*' like LC 10 '*' (which requires a preceding char).
  • Forgetting dp[0][j] init — patterns like '***' must match empty s.
  • Greedy approaches without state — can fail on ambiguous patterns.

Follow-up questions

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

  • Greedy two-pointer with backtrack — O(s + p) average.
  • Regular Expression Matching (LC 10) — different semantics.
  • Implement strStr (LC 28) — no wildcards.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

LC 44 vs LC 10?

LC 44 '*' matches any sequence on its own (no preceding char required). LC 10 '*' refers to zero+ of the preceding element.

Greedy alternative?

Two-pointer with a 'star saved' position. When mismatch, backtrack to after the last star and advance s. O(s + p) average, easy to implement after the DP.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →