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 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

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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →