DSA problem
Wildcard Matching
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). This is the simpler cousin of regular expression matching: * here behaves like .* from regex, and there is no concept of "zero or more of the previous character".
Naive backtracking explores every possible split of *, producing exponential blow-up on inputs like s = "aaaaaaab", p = "*a*a*a*a*b". Dynamic programming systematically resolves the overlap.
Define dp[i][j] as a boolean meaning "s[0..i) matches p[0..j)". The recurrences:
- If
p[j-1] == '*':dp[i][j] = dp[i][j-1] || dp[i-1][j]— match empty sequence (drop the*) OR consume one more character (stay with the same*). - If
p[j-1] == '?'orp[j-1] == s[i-1]:dp[i][j] = dp[i-1][j-1]. - Else:
dp[i][j] = false.
Initialize dp[0][0] = true and let leading * characters in the pattern continue to match the empty string. The algorithm runs in O(m * n) time and O(m * n) space (compressible to O(n)). A greedy two-pointer alternative runs in average linear time but the DP is the canonical, easy-to-verify approach.
Examples
s = "aa", p = "a"falses = "aa", p = "*"trues = "cb", p = "?a"falseConstraints
- 0 <= s.length, p.length <= 2000
- s contains only lowercase English letters.
- p contains only lowercase English letters, '?' or '*'.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.