#44
Wildcard Matching
Hard 2D DP on string and pattern
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a pattern with '?' (any one character) and '*' (any sequence, including empty) matches the whole string.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does a pattern with ? and * match the whole string?
Why this works: dp[i][j] for prefixes. '*' matches nothing (left cell) or one more letter (cell above).
Example: s "adceb", p "*a*b"
'*' empty, 'a' matches, '*' eats "dce", 'b' matches → true✦Hints open one at a time
dp[i][j] = first i chars of s match first j chars of p.
'*' either matches nothing (dp[i][j−1]) or one more character (dp[i−1][j]).
A pattern prefix of only '*' matches the empty string.
↗Approach
dp[0][0] = true; dp[0][j] true while p[0..j) is all '*'. For '*' use the two options above; for '?' or an equal letter use dp[i−1][j−1].
</>Solution (Java)
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length(), m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int j = 1; j <= m && p.charAt(j - 1) == '*'; j++) dp[0][j] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char pc = p.charAt(j - 1);
if (pc == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; // empty, or eat one more char
else if (pc == '?' || pc == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[n][m];
}
}!Common mistake
Forgetting the leading-'*' row, so patterns like "*a" fail to match.
Complexity
- Time: O(n·m).
- Space: O(n·m).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon