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 <= 2000s contains only lowercase English letters.p contains only lowercase English letters, '?' or '*'.Problem Overview: Given a string s and a pattern p, determine whether the pattern matches the entire string. The pattern supports two wildcards: ? matches any single character and * matches any sequence of characters (including empty).
Approach 1: Dynamic Programming (Time: O(m × n), Space: O(m × n))
Dynamic programming treats this as a prefix matching problem. Create a 2D table dp[i][j] where i represents the first i characters of the string and j represents the first j characters of the pattern. If characters match or the pattern contains ?, inherit the value from dp[i-1][j-1]. When encountering *, two possibilities exist: match zero characters (dp[i][j-1]) or match one more character (dp[i-1][j]). Fill the table iteratively from smaller prefixes to larger ones. This approach handles every edge case and is straightforward to reason about, making it a common interview solution when discussing Dynamic Programming on String problems.
Approach 2: Greedy Algorithm with Backtracking (Time: O(m + n) average, Space: O(1))
The greedy approach scans the string and pattern using two pointers. When characters match or the pattern contains ?, move both pointers forward. When encountering *, record its position and the corresponding string index, then advance the pattern pointer. If a mismatch occurs later, backtrack to the most recent * and expand its match by one more character in the string. This effectively lets * absorb characters until alignment is possible again. The method avoids building a DP table and runs in linear time for most inputs. It relies on the greedy property of * and is commonly discussed under Greedy techniques with a touch of controlled backtracking.
Recommended for interviews: Dynamic Programming is the safest answer because it systematically handles all matching cases and demonstrates strong understanding of state transitions. After presenting DP, mention the greedy two‑pointer optimization. Showing both approaches signals that you understand the problem deeply and can move from brute-force state exploration to an optimized linear scan.
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:
Fill the table using the following rules:
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m + n) due to possible backtracking
Space Complexity: O(1) requiring constant storage for indices.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m*n) where m and n are the lengths of s and p, respectively. |
| Greedy Algorithm Approach | Time Complexity: O(m + n) due to possible backtracking |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(m × n) | O(m × n) | General solution that handles all edge cases clearly; ideal for explaining reasoning in interviews. |
| Greedy Two-Pointer with Backtracking | O(m + n) average | O(1) | When optimizing for constant space and faster scans; effective when many '*' patterns appear. |
DP 34. Wildcard Matching | Recursive to 1D Array Optimisation 🔥 • take U forward • 204,658 views views
Watch 9 more video solutions →Practice Wildcard Matching with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor