Watch 10 video solutions for Wildcard Matching, a hard level problem involving String, Dynamic Programming, Greedy. This walkthrough by take U forward has 204,658 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |