Skip to main content
Talentd

Wildcard Matching - Solution & Explanation

HardStringDynamic ProgrammingGreedyRecursion34 min readAsked at: Amazon, Microsoft, Meta +14
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Wildcard Matching checks whether an entire string s matches a pattern p that may contain two special characters: ? (matches any single character) and * (matches any sequence of characters, including empty). The goal is to return true if the whole string can be matched by the pattern, otherwise false.

Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)

This approach models the problem as a state transition using dynamic programming. Create a 2D table dp[i][j] where each state represents whether the first i characters of s match the first j characters of p. If characters match or the pattern has ?, the result depends on the previous diagonal state dp[i-1][j-1]. When encountering *, two possibilities exist: treat it as matching zero characters (dp[i][j-1]) or match one more character from the string (dp[i-1][j]). Initialization is critical because leading * characters can match an empty string. This solution systematically evaluates all subproblems and guarantees correctness for every edge case.

DP is reliable for interview discussion because it clearly expresses the recursive relationship between pattern and string prefixes. The tradeoff is memory usage: storing a full table requires O(m*n) space, though it can be optimized to O(n) by keeping only the previous row.

Approach 2: Greedy Two-Pointer Algorithm (O(m+n) time, O(1) space)

A faster solution uses a greedy strategy with two pointers scanning the string and pattern. Track four values: the current index in s, the current index in p, the most recent * position in the pattern, and the position in the string where that star started matching. When characters match or the pattern has ?, advance both pointers. When encountering *, record its position and attempt to match zero characters first. If a mismatch occurs later, backtrack to the last * and expand its match by one additional character in the string.

This works because * can represent any substring length, so the algorithm greedily tries minimal matches and only expands when needed. The scan never moves backward in the pattern except to the stored star position, which keeps the runtime linear. The method relies heavily on careful pointer management and is commonly categorized under string processing techniques.

Recommended for interviews: Interviewers often expect the Dynamic Programming reasoning first because it demonstrates understanding of overlapping subproblems and pattern matching logic. After that, presenting the Greedy two-pointer optimization shows deeper algorithmic insight since it reduces complexity to O(m+n) time and O(1) space. Showing both approaches signals strong problem-solving depth.

Approach 1: Dynamic Programming Approach

The dynamic programming approach uses a 2D table to store results of subproblems. We define dp[i][j] as True if the first i characters in the string s can be matched by the first j characters of the pattern p.

Base Cases:

  • dp[0][0] is True because an empty pattern matches an empty string.
  • dp[0][j] is True if p[j-1] is '*', otherwise False.
  • dp[i][0] is False because a non-empty string cannot be matched by an empty pattern.

Fill the table using the following rules:

  • If p[j-1] is '*', dp[i][j] is True if dp[i-1][j] or dp[i][j-1] is True.
  • If p[j-1] is '?' or p[j-1] == s[i-1], dp[i][j] is True if dp[i-1][j-1] is True.

The code initializes a boolean matrix dp such that dp[i][j] is True if the first i characters of s match with the first j characters of p.

We handle '*' using two cases: either it matches the empty sequence, so we look to the left; or it matches one or more characters, so we look above.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*n) where m and n are the lengths of s and p, respectively.
Space Complexity: O(m*n) due to the storage of the dp table.

Try this approach in the editor →

Approach 2: Greedy Algorithm Approach

The greedy algorithm approach tracks the position of the last '*' in the pattern and attempts to match remaining characters greedily. We maintain two pointers, one for the string and one for the pattern. When encountering '*', we remember the positions of both pointers in order to backtrack if needed.

If characters in p and s match or if the pattern has '?', both pointers are incremented. For '*', we shift the pattern pointer and remember indices for future potential matches. If there's a mismatch after '*', we use these remembered indices to backtrack.

This greedy algorithm utilizes backtracking facilitated by the last seen '*' position to handle mismatches, allowing us to efficiently manage sequences that can contain many wildcard characters.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m + n) due to possible backtracking
Space Complexity: O(1) requiring constant storage for indices.

Try this approach in the editor →

Approach 3: Memoization Search

We design a function dfs(i, j), which represents whether the string s starting from the i-th character matches the string p starting from the j-th character. The answer is dfs(0, 0).

The execution process of the function dfs(i, j) is as follows:

  • If i geq len(s), then dfs(i, j) is true only when j geq len(p) or p[j] = '*' and dfs(i, j + 1) is true.
  • If j geq len(p), then dfs(i, j) is false.
  • If p[j] = '*', then dfs(i, j) is true if and only if dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1) is true.
  • Otherwise, dfs(i, j) is true if and only if p[j] = '?' or s[i] = p[j] and dfs(i + 1, j + 1) is true.

To avoid repeated calculations, we use the method of memoization search and store the result of dfs(i, j) in a hash table.

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the lengths of the strings s and p, respectively.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Approach 4: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming.

Define f[i][j] to represent whether the first i characters of string s match the first j characters of string p. Initially, f[0][0] = true, indicating that two empty strings are matching. For j \in [1, n], if p[j-1] = '*', then f[0][j] = f[0][j-1].

Next, we consider the case of i \in [1, m] and j \in [1, n]:

  • If p[j-1] = '*', then f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1].
  • Otherwise, f[i][j] = (p[j-1] = '?' \lor s[i-1] = p[j-1]) \land f[i-1][j-1].

The final answer is f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the lengths of the strings s and p, respectively.

Code

PythonJavaC++GoTypeScriptPHP

Python

Java

C++

Go

TypeScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(m*n) where m and n are the lengths of s and p, respectively.
Space Complexity: O(m*n) due to the storage of the dp table.

Greedy Algorithm Approach

Time Complexity: O(m + n) due to possible backtracking
Space Complexity: O(1) requiring constant storage for indices.

Memoization Search—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(m*n)O(m*n) or O(n)General case when you want a clear, systematic solution that handles all edge cases
Greedy Two-PointerO(m+n)O(1)Optimal solution when performance matters and pattern contains many '*' wildcards

Video Solution

DP 34. Wildcard Matching | Recursive to 1D Array Optimisation 🔥 • take U forward • 298,569 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Wildcard Matching easy or hard?
Wildcard Matching is classified as a hard problem because it combines string parsing, edge-case handling, and algorithm optimization. Understanding the DP transition rules is manageable, but discovering the linear-time greedy strategy requires deeper insight.
How to solve Wildcard Matching in O(n)?
An O(m+n) solution uses two pointers and a greedy strategy. When a '*' appears in the pattern, store its position and the corresponding string index. If a mismatch happens later, backtrack to the stored star and expand the match by one character. This avoids building a DP table and keeps memory usage constant.
What is the best approach for Wildcard Matching?
The most widely taught solution is Dynamic Programming because it clearly models matching between prefixes of the string and pattern. However, the optimal solution uses a greedy two-pointer technique with backtracking to the last '*' position. That method runs in O(m+n) time and O(1) space, making it more efficient for large inputs.
What data structure is used in Wildcard Matching?
The Dynamic Programming approach uses a 2D boolean DP table to store match states between prefixes of the string and pattern. The greedy solution instead relies on pointer tracking and a few integer variables, avoiding additional data structures entirely.
What is the time complexity of Wildcard Matching?
The Dynamic Programming approach runs in O(m*n) time where m is the length of the string and n is the length of the pattern. The optimized greedy algorithm reduces this to O(m+n) by scanning both strings once while tracking the most recent '*' position.
Wildcard Matching Python or Java solution approach
Both Python and Java implementations usually follow either the DP table method or the greedy two-pointer algorithm. The DP version uses nested loops to fill a boolean matrix, while the greedy version uses pointer indices and star tracking variables to simulate pattern expansion.
Is Wildcard Matching asked at Google, Amazon, or Meta?
Wildcard-style pattern matching problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants test string processing, backtracking, and dynamic programming skills, making this problem a common hard-level interview question.

Ready to solve this problem?

Practice Wildcard Matching with our built-in code editor and test cases.

Practice on FleetCode
Previous

Regular Expression Matching

Next

Substring Matching Pattern