Wildcard Matching
Difficulty: Hard
Problem Statement
Given an input string s
and a pattern p
, implement wildcard matching with support for the following:
'?'
matches any single character.'*'
matches any sequence of characters (including an empty sequence).
The match should cover the entire input string, not just a partial match.
Examples
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 of characters.
Example 3:
Input: s = "cb"
, p = "?a"
Output: false
Explanation: '?'
matches 'c'
, but 'a'
does not match 'b'
.
Constraints
0 <= s.length, p.length <= 2000
s
contains only lowercase English letters.p
contains only lowercase English letters,'?'
, or'*'
.
Approach: Dynamic Programming (Bottom-Up)
To efficiently solve this problem, we use Dynamic Programming (DP).
Step 1: Define the DP Table
We create a 2D table dp[i][j]
, where:
dp[i][j] = true
if the firsti
characters ofs
match the firstj
characters ofp
.
Why DP?
'*'
can match multiple characters, requiring us to track results of smaller subproblems.- A table-based approach avoids redundant calculations.
Step 2: Base Cases
- Empty string matches an empty pattern:
dp[0][0] = true
(Empty pattern matches an empty string).
- Handling patterns with leading '*':
- If
p[j-1] == '*'
, thendp[0][j] = dp[0][j-1]
(i.e.,'*'
behaves as an empty match).
- If
Step 3: Filling the DP Table
We iterate through s
and p
, applying these rules:
- Character Matches (
s[i-1] == p[j-1]
orp[j-1] == '?'
)- If characters match or
p[j-1] == '?'
, then:dp[i][j] = dp[i-1][j-1];
- If characters match or
- Handling
'*'
(Matches Any Sequence)'*'
can:- Match zero characters →
dp[i][j] = dp[i][j-1]
- Match one or more characters →
dp[i][j] = dp[i-1][j]
- Match zero characters →
- Formula:
dp[i][j] = dp[i-1][j] || dp[i][j-1];
C# Implementation
using System;
public class Solution {
public bool IsMatch(string s, string p) {
int m = s.Length, n = p.Length;
bool[,] dp = new bool[m + 1, n + 1];
// Base case: Empty string matches empty pattern
dp[0, 0] = true;
// Fill first row for patterns with '*'
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[0, j] = dp[0, j - 1]; // '*' matches empty sequence
}
}
// Fill DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
dp[i, j] = dp[i - 1, j - 1]; // Match single character or '?'
} else if (p[j - 1] == '*') {
dp[i, j] = dp[i - 1, j] || dp[i, j - 1]; // '*' matches one or more OR empty
}
}
}
return dp[m, n];
}
}
// Example Usage
class Program {
static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.IsMatch("aa", "a")); // false
Console.WriteLine(solution.IsMatch("aa", "*")); // true
Console.WriteLine(solution.IsMatch("cb", "?a")); // false
Console.WriteLine(solution.IsMatch("adceb", "*a*b")); // true
Console.WriteLine(solution.IsMatch("acdcb", "a*c?b"));// false
}
}
Complexity Analysis
Approach | Time Complexity | Space Complexity |
---|---|---|
DP Table | O(m × n) |
O(m × n) |
Optimized DP (1D Array) | O(m × n) |
O(n) |
Optimized Approach (Space Reduction)
Instead of a 2D table, we can use two 1D arrays (current and previous row), reducing space from O(m × n)
to O(n)
.
Example Walkthrough
Example 1: s = "aa"
, p = "a"
a | |
---|---|
a | T |
a | F |
Output: false
Example 2: s = "aa"
, p = "*"
* | |
---|---|
a | T |
a | T |
Output: true
Edge Cases Considered
✅ Empty s
or p
✅ Pattern with multiple '*'
✅ Pattern with '?'
✅ No wildcards
Summary
✅ DP Table efficiently stores subproblem results.
✅ Handles '*'
and '?'
effectively.
✅ Optimized Space Approach reduces memory usage.
This C# solution ensures efficient wildcard pattern matching! 🚀