Definition
Wildcard Matching uses 2D DP where dp[i][j] means the first i text chars match the first j pattern chars.
- Star is standalone: it matches any sequence including empty. dp[i][j] = dp[i-1][j] (absorb one more) OR dp[i][j-1] (match empty).
- Question mark or exact character match requires dp[i-1][j-1] when the single char matches.
- First row is true across a leading run of stars because each star can match empty.
- Time is O(m * n) and space reducible to O(n).
- Greedy alternative with a saved star position solves in O(m * n) worst case but O(1) space.
A file-name matcher at National Bank of India filters statement files by a glob pattern. A question mark matches exactly one character and a star matches any run of characters. At a star the matcher can either swallow one more character or declare the star finished.
Understanding the Concepts
What is the Wildcard Matching Problem?
Implement pattern matching where ? matches any single character and * matches any sequence of characters including the empty sequence. The match must cover the entire input string.
At National Bank of India, a batch processor filters statement files by a glob pattern like stmt_2024_*.csv or report_??_final.pdf.
package com.bank.service;
public class WildcardMatching {
public static boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
// First row: leading stars match empty text
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char pc = p.charAt(j - 1);
if (pc == '*') {
dp[i][j] = dp[i - 1][j] // star absorbs one more char
|| dp[i][j - 1]; // star matches empty
} else if (pc == '?' || pc == s.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // single char match
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(isMatch("statement_2024", "stat*2024")); // true
System.out.println(isMatch("report_ab", "report_??")); // true
System.out.println(isMatch("data", "da*ta*")); // true
}
}
true
true
true
Why Is This Simpler Than Regex Matching?
Wildcard Matching is simpler because the star is standalone: it matches any sequence by itself, not tied to a preceding element. In Regex Matching, a* means zero or more as, so the star modifies the previous character and the DP must look back two positions. Here, the star directly absorbs characters or matches empty.
package com.bank.core;
public class WildcardVsRegex {
// Wildcard *: dp[i][j] = dp[i-1][j] || dp[i][j-1]
// - absorb one char OR match empty
// - standalone, no preceding element needed
// Regex *: dp[i][j] = dp[i][j-2] || (prevMatch && dp[i-1][j])
// - zero occurrences of preceding element OR one more occurrence
// - tied to preceding element
}
How Does the Star Case Work?
The star has two branches. dp[i-1][j] means the star absorbs the current text character and keeps matching (star stays, text advances). dp[i][j-1] means the star matches the empty sequence (pattern advances past star, text stays).
package com.bank.core;
public class StarCaseWildcard {
public static void main(String[] args) {
// Text: "abc", Pattern: "a*c"
// Star at j=2:
// dp[1][2] = dp[0][2] (absorb 'a') || dp[1][1] (match empty)
// dp[2][2] = dp[1][2] (absorb 'b') || dp[2][1] (match empty)
// dp[3][2] = dp[2][2] (absorb 'c') || dp[3][1] (match empty)
System.out.println(WildcardMatching.isMatch("abc", "a*c")); // true
}
}
true
How Is This Different from Regex Matching?
| Aspect | Wildcard Matching | Regex Matching |
|---|---|---|
| Star meaning | Any sequence (standalone) | Zero or more of preceding element |
| Star zero case | dp[i][j-1] (skip star) | dp[i][j-2] (skip x* pair) |
| Star one-more case | dp[i-1][j] (absorb char) | dp[i-1][j] if preceding matches |
| Single match | ? or exact char | . or exact char |
| Complexity | O(m*n) | O(m*n) |
| Space-optimal variant | Greedy two-pointer O(1) space | No known O(1) space variant |
What Are the Edge Cases?
Edge cases include: pattern is a single star (matches everything), pattern has no wildcards (exact match required), text is empty with a star pattern (matches), and consecutive stars.
package com.bank.core;
public class WildcardEdgeCases {
public static void main(String[] args) {
System.out.println(WildcardMatching.isMatch("anything", "*")); // true
System.out.println(WildcardMatching.isMatch("exact", "exact")); // true
System.out.println(WildcardMatching.isMatch("exact", "exac")); // false
System.out.println(WildcardMatching.isMatch("", "***")); // true
System.out.println(WildcardMatching.isMatch("", "?")); // false
}
}
true
true
false
true
false
What About the Greedy Two-Pointer Approach?
The greedy approach uses two pointers (one for text, one for pattern) and remembers the position of the last star and the text position when it was encountered. When a mismatch occurs, it backtracks to the last star and advances the text pointer by one.
package com.bank.core;
public class WildcardGreedy {
public static boolean isMatch(String s, String p) {
int si = 0, pi = 0;
int starIdx = -1, matchIdx = -1;
while (si < s.length()) {
if (pi < p.length() && (p.charAt(pi) == '?' || p.charAt(pi) == s.charAt(si))) {
si++; pi++; // single char match
} else if (pi < p.length() && p.charAt(pi) == '*') {
starIdx = pi; matchIdx = si; // remember star position
pi++; // try matching empty first
} else if (starIdx != -1) {
pi = starIdx + 1; // backtrack to after star
matchIdx++; // star absorbs one more char
si = matchIdx;
} else {
return false;
}
}
while (pi < p.length() && p.charAt(pi) == '*') pi++; // trailing stars
return pi == p.length();
}
}
This approach uses O(1) extra space but has the same O(m*n) worst-case time due to backtracking.
What About Space Optimization for DP?
Since each row depends only on the previous row, we can reduce space from O(m*n) to O(n) using two rolling arrays.
package com.bank.core;
public class WildcardSpaceOpt {
public static boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[] prev = new boolean[n + 1];
prev[0] = true;
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') prev[j] = prev[j - 1];
}
for (int i = 1; i <= m; i++) {
boolean[] curr = new boolean[n + 1];
for (int j = 1; j <= n; j++) {
char pc = p.charAt(j - 1);
if (pc == '*') {
curr[j] = prev[j] || curr[j - 1];
} else if (pc == '?' || pc == s.charAt(i - 1)) {
curr[j] = prev[j - 1];
}
}
prev = curr;
}
return prev[n];
}
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Regex Matching: star modifies the preceding element instead of being standalone.
- Implement glob matching with
**for directory recursion. - Compare DP vs greedy: DP is cleaner, greedy uses O(1) space.
- Handle escaped characters:
\*and\?should match literal star and question mark.
package com.bank.core;
public class WildcardFollowUps {
// Regex: star tied to preceding element
// Glob **: recursive directory matching
// Escaped chars: treat \* as literal *
// DP vs Greedy: same time, greedy is O(1) space
}
Visual Overview
DP Table for s="adceb", p="*a*b":
"" * a * b
"" [ T T F F F ]
a [ F T T T F ]
d [ F T F T F ]
c [ F T F T F ]
e [ F T F T F ]
b [ F T F T T ]
Star Logic (standalone):
┌─────────────────────────────────┐
│ dp[i][j] for * at position j: │
│ │
│ dp[i-1][j]: absorb one char │
│ (star keeps going) │
│ ↑ from cell above │
│ │
│ dp[i][j-1]: match empty │
│ (star is done) │
│ ← from cell left │
└─────────────────────────────────┘
Key Takeaway
Wildcard Matching is a 2D DP problem that is simpler than Regex Matching because the star here is standalone and matches any sequence directly, rather than being tied to a preceding element. I define dp[i][j] as whether the first i characters of the text match the first j characters of the pattern. The star has two branches: absorb one more text character (cell above) or match empty (cell left). A question mark or exact character match inherits the diagonal.
The first row is true across a leading run of stars because each star can match the empty text. The body fills left to right, top to bottom, and the answer is the bottom-right cell. Space reduces to O(n) with rolling arrays.
At National Bank of India, a batch processor filtered statement file names by a glob pattern where a question mark matched one character and a star matched any run. Because a star can match nothing or a long stretch, a plain scan cannot decide where it should stop, which is why DP is needed.
The greedy two-pointer variant with a saved star position is a strong follow-up that achieves the same worst-case time with O(1) space. Explaining both approaches shows the interviewer you understand the tradeoff between clarity and space.
Remember one sentence: star absorbs one more char from above or matches empty from the left, and question mark or exact char matches via the diagonal.
---