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 Sam K., 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

More Recursion practice problems

See all Recursion problems →