Scale Engineer

Wildcard Matching

Hard
#0044Time: O(2^(m+n))Space: O(m + n)19 companies
Patterns
RecursionDynamic ProgrammingGreedy
Data structures
String
Companies
AdobeAmazonAppleBloomberg

Prompt

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

 

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

 

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach directly translates the problem's definition into a recursive function. It explores all possible matching paths by making recursive calls. When a * is encountered in the pattern, the function branches into two recursive calls to explore both possibilities: the * matching an empty sequence, and the * matching one or more characters. This brute-force exploration of all paths leads to a very high time complexity.

Algorithm

  • Define a recursive function isMatch(s_idx, p_idx) that checks if s from index s_idx matches p from index p_idx.
  • Base Case 1: If the pattern pointer p_idx reaches the end, the match is successful only if the string pointer s_idx has also reached the end.
  • Base Case 2: If the string pointer s_idx reaches the end, the remainder of the pattern must consist solely of * characters to match an empty string.
  • Recursive Step for *: If the current pattern character p[p_idx] is *, there are two possibilities:
    1. The * matches an empty sequence. We move to the next character in the pattern: isMatch(s_idx, p_idx + 1).
    2. The * matches one or more characters. We consume a character from the string and stay at the same * in the pattern: isMatch(s_idx + 1, p_idx). The result is true if either path succeeds.
  • Recursive Step for ? or matching characters: If p[p_idx] is ? or equals s[s_idx], we advance both pointers: isMatch(s_idx + 1, p_idx + 1).
  • Mismatch: If none of the above, it's a mismatch, return false.

Walkthrough

The core idea is to define a helper function, say solve(i, j), which returns true if the substring s[i:] matches the sub-pattern p[j:]. The logic proceeds by comparing characters at s[i] and p[j].

  • If p[j] is a normal character, it must match s[i]. If they match, we recurse on solve(i+1, j+1).
  • If p[j] is ?, it matches any character, so we recurse on solve(i+1, j+1).
  • If p[j] is *, it creates a choice. The * can match nothing, so we check solve(i, j+1). Or, it can match the character s[i] (and possibly more), so we check solve(i+1, j). If either of these recursive calls returns true, then we have a match.

This method is simple to conceptualize but suffers from massive performance issues due to overlapping subproblems, where the function recalculates solve(i, j) for the same i and j multiple times.

class Solution {    public boolean isMatch(String s, String p) {        return solve(s, p, 0, 0);    }     private boolean solve(String s, String p, int i, int j) {        // If pattern is exhausted, string must also be exhausted for a match.        if (j == p.length()) {            return i == s.length();        }         char pChar = p.charAt(j);         if (pChar == '*') {            // Option 1: '*' matches empty sequence. Move to next pattern char.            if (solve(s, p, i, j + 1)) {                return true;            }            // Option 2: '*' matches current string char. Move to next string char.            // This is only possible if string is not exhausted.            if (i < s.length() && solve(s, p, i + 1, j)) {                return true;            }        } else {            // Check for a match of the current characters.            boolean firstMatch = (i < s.length()) && (pChar == '?' || pChar == s.charAt(i));            if (firstMatch && solve(s, p, i + 1, j + 1)) {                return true;            }        }         return false;    }}

Complexity

Time

O(2^(m+n))

Space

O(m + n)

Trade-offs

Pros

  • Simple to understand and implement directly from the problem statement.

  • Clearly illustrates the recursive nature of the problem.

Cons

  • Extremely inefficient due to exponential time complexity.

  • Leads to a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.

  • Computes the same subproblems repeatedly.

Solutions

using System.Linq ; public class Solution { public bool IsMatch ( string s , string p ) { if ( p . Count ( ch => ch != '*' ) > s . Length ) { return false ; } bool [,] f = new bool [ s . Length + 1 , p . Length + 1 ]; bool [] d = new bool [ s . Length + 1 ]; // d[i] means f[0, j] || f[1, j] || ... || f[i, j] for ( var j = 0 ; j <= p . Length ; ++ j ) { d [ 0 ] = j == 0 ? true : d [ 0 ] && p [ j - 1 ] == '*' ; for ( var i = 0 ; i <= s . Length ; ++ i ) { if ( j == 0 ) { f [ i , j ] = i == 0 ; continue ; } if ( p [ j - 1 ] == '*' ) { if ( i > 0 ) { d [ i ] = f [ i , j - 1 ] || d [ i - 1 ]; } f [ i , j ] = d [ i ]; } else if ( p [ j - 1 ] == '?' ) { f [ i , j ] = i > 0 && f [ i - 1 , j - 1 ]; } else { f [ i , j ] = i > 0 && f [ i - 1 , j - 1 ] && s [ i - 1 ] == p [ j - 1 ]; } } } return f [ s . Length , p . Length ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem