Skip to main content

89. Wildcard Matching

hardAsked at Salesforce

Implement wildcard pattern matching with '?' and '*'. Salesforce uses this in their permission-set glob matching for object access rules.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses glob matching in permission-set object access rules.
  • LeetCode Discuss (2025)— Hard DP/greedy stretch question.

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

Try matching, try '?' (single any), try '*' as zero or more.

Time
Exponential
Space
O(s+p)
// Exponential. Need DP.

Tradeoff: TLE.

2. Greedy backtracking

Walk both. On match, advance both. On '*', record positions and try matching with zero chars. On mismatch, backtrack to last '*' and consume one more char.

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

Tradeoff: O(1) extra space; better than DP in practice. The starIdx/sTmpIdx pair tracks the last '*' position for backtracking.

Salesforce-specific tips

Salesforce uses glob matching in permission-set object access rules — '*' matches any object, '?' matches any single character (rarely used). They grade on whether you can articulate the greedy backtracking strategy. Bonus signal: discuss the 2D DP alternative (O(m*n) space) for comparison.

Common mistakes

  • Confusing '*' (any sequence) with regex '*' (any number of previous char).
  • Not handling trailing '*' in the pattern at the end — must skip them.
  • Backtracking too far — the starIdx/sTmpIdx pair must track the LAST '*'.

Follow-up questions

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

  • Regular Expression Matching (LC 10).
  • Edit Distance (LC 72).
  • DP version with explicit table.

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 the greedy approach?

Because '*' can match any sequence, we can defer the decision: try matching with the current alignment, and if it fails, expand the '*' by one more char.

What's the worst case?

Pathological patterns like 'a*a*a*...*b' against a long 'aaaa...' string. The backtracking re-visits positions, leading to O(m*n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →