Skip to main content

44. Wildcard Matching

hard

Match a string against a pattern with '?' (any single character) and '*' (any sequence including empty). Like Regex Matching but simpler — the '*' here is global, not bound to a preceding character.

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

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

Explanation: "a" does not match the entire string "aa".

Example 2

Input
s = "aa", p = "*"
Output
true

Explanation: '*' matches any sequence.

Example 3

Input
s = "cb", p = "?a"
Output
false

Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse on (i, j). Memoize.

Hint 2

If p[j] is letter or '?': must match a char. Recurse (i+1, j+1) if i in range and characters match.

Hint 3

If p[j] is '*': two branches — (a) treat '*' as empty -> (i, j+1), (b) consume one char of s -> (i+1, j).

Hint 4

Base: j out of bounds -> i must also be out of bounds. i out of bounds -> remaining pattern must be all '*'.

Solution approach

Reveal approach

Recursive match(i, j): if j == p.length, return i == s.length. If i == s.length, return remaining p[j..] are all '*'. If p[j] == '?' or (i < s.length and p[j] == s[i]): return match(i + 1, j + 1). If p[j] == '*': return match(i, j + 1) (zero match) OR match(i + 1, j) (consume one). Otherwise return false. Memoize on (i, j). The iterative bottom-up DP version uses dp[i][j] = match(i, j); time O(m * n), space O(m * n) or O(n) with rolling array. A linear-time greedy version also works but it's trickier and rarely needed in interviews.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • recursion
  • memoization
  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Google
  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Wildcard Matching and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →