Skip to main content

44. Wildcard Matching

hard

Match a string against a pattern with '?' (any single char) and '*' (any sequence including empty). Two-string DP where '*' is the branching star: skip it, or consume one more char and stay on it.

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

dp[i][j] = does the first i chars of s match the first j chars of p?

Hint 2

Base: dp[0][0] = true. dp[0][j] is true only if p[0..j-1] is all '*'.

Hint 3

If p[j-1] is a letter or '?': dp[i][j] = dp[i-1][j-1] AND (p[j-1] == '?' OR p[j-1] == s[i-1]).

Hint 4

If p[j-1] == '*': dp[i][j] = dp[i][j-1] (use '*' as empty) OR dp[i-1][j] (use '*' to absorb one more char).

Solution approach

Reveal approach

Bottom-up DP over a 2D boolean table dp[m+1][n+1] with m = len(s) and n = len(p). dp[i][j] is true iff the first i chars of s match the first j chars of p. Initialize dp[0][0] = true; dp[0][j] = dp[0][j-1] AND p[j-1] == '*'. For each (i, j): if p[j-1] is '?' or matches s[i-1], dp[i][j] = dp[i-1][j-1]. If p[j-1] == '*', dp[i][j] = dp[i][j-1] OR dp[i-1][j] — the first option treats '*' as the empty sequence, the second extends '*' to consume s[i-1]. Else dp[i][j] = false. Return dp[m][n]. Space optimization: only the previous row is needed, so O(n) extra space works. A two-pointer greedy with backtracking also solves the problem in O(m + n) average time.

Complexity

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

Related patterns

  • dynamic-programming
  • string-dp
  • two-strings-table

Related problems

Asked at

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

  • Meta
  • Microsoft
  • Bloomberg
  • Google

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →