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 '*'.Wildcard Matching asks whether a string matches a pattern containing special characters like ? (matches any single character) and * (matches any sequence of characters, including empty). Because * can represent multiple possibilities, a brute-force recursive approach quickly becomes inefficient.
A common strategy is Dynamic Programming, where dp[i][j] represents whether the first i characters of the string match the first j characters of the pattern. Transitions depend on whether the current pattern character is a normal character, ?, or *. The * case allows matching zero characters or extending a previous match.
An optimized greedy two-pointer technique can also be used. It tracks the last position of * and backtracks when mismatches occur, effectively simulating pattern expansion without building a full DP table.
The DP approach provides clarity but uses more memory, while the greedy solution improves space usage. Typical complexities are O(n × m) for DP and O(n) time with constant space for the greedy strategy in most practical cases.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming | O(n × m) | O(n × m) |
| Greedy Two-Pointer | O(n) | O(1) |
take U forward
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:
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.
1public class Solution {
2 public boolean isMatch(String s, String p) {
3 int m = s.lengthThe core idea is the same dynamic programming approach. The Java implementation makes use of arrays to store intermediate match results for substrings of s and p.
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.
Time Complexity: O(m + n) due to possible backtracking
Space Complexity: O(1) requiring constant storage for indices.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Wildcard Matching is considered a classic hard string problem and has appeared in interviews at top tech companies. It tests understanding of dynamic programming, pattern matching, and careful handling of edge cases involving '*'.
A common optimal approach uses dynamic programming to track matches between string prefixes and pattern prefixes. However, an optimized greedy two-pointer strategy with backtracking on '*' can achieve linear time in many cases with constant space.
Dynamic programming typically uses a 2D table to store intermediate match results between the string and pattern. For optimized solutions, only pointers and a few variables are needed to track the last '*' position and backtracking points.
The '?' character matches exactly one character in the input string. The '*' character is more flexible and can match any sequence of characters, including an empty sequence.
The Python implementation effectively replicates the greedy mechanism, seeking to pair current text components with 'p' elements using only essential backtracking when necessary.