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: 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.
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.
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.
Time Complexity: O(m + n) due to possible backtracking
Space Complexity: O(1) requiring constant storage for indices.
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:
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.j geq len(p), then dfs(i, j) is false.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.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.
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]:
p[j-1] = '*', then f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1].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.
| 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 |
| Memoization Search | — |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(m*n) | O(m*n) or O(n) | General case when you want a clear, systematic solution that handles all edge cases |
| Greedy Two-Pointer | O(m+n) | O(1) | Optimal solution when performance matters and pattern contains many '*' wildcards |
DP 34. Wildcard Matching | Recursive to 1D Array Optimisation 🔥 • take U forward • 277,086 views views
Watch 9 more video solutions →Practice Wildcard Matching with our built-in code editor and test cases.
Practice on FleetCode