Problem Description
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).
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. Example 3: Input: s = "cb", p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Python Solution
def isMatch(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# Handle patterns starting with *
for j in range(1, n + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-1]
# Fill dp table
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1]
elif p[j-1] == '?' or s[i-1] == p[j-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n]Java Solution
class Solution {
public 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;
// Handle patterns starting with *
for (int j = 1; j <= n; j++) {
if (p.charAt(j-1) == '*') {
dp[0][j] = dp[0][j-1];
}
}
// Fill dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j-1) == '*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
} else if (p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[m][n];
}
}C++ Solution
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector> dp(m + 1, vector(n + 1, false));
dp[0][0] = true;
// Handle patterns starting with *
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*') {
dp[0][j] = dp[0][j-1];
}
}
// Fill dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
} else if (p[j-1] == '?' || s[i-1] == p[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[m][n];
}
}; JavaScript Solution
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
const m = s.length, n = p.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(false));
dp[0][0] = true;
// Handle patterns starting with *
for (let j = 1; j <= n; j++) {
if (p[j-1] === '*') {
dp[0][j] = dp[0][j-1];
}
}
// Fill dp table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j-1] === '*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
} else if (p[j-1] === '?' || s[i-1] === p[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[m][n];
};C# Solution
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];
dp[0,0] = true;
// Handle patterns starting with *
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*') {
dp[0,j] = dp[0,j-1];
}
}
// Fill dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*') {
dp[i,j] = dp[i-1,j] || dp[i,j-1];
} else if (p[j-1] == '?' || s[i-1] == p[j-1]) {
dp[i,j] = dp[i-1,j-1];
}
}
}
return dp[m,n];
}
}Complexity Analysis
- Time Complexity: O(m * n) where m and n are the lengths of the strings
- Space Complexity: O(m * n) for the dp table
Solution Explanation
This solution uses dynamic programming to solve the wildcard matching problem. Here's how it works:
- Initialize dp table:
- dp[i][j] represents if s[0:i] matches p[0:j]
- Base case: empty pattern matches empty string
- Handle patterns starting with *:
- If pattern starts with *, it can match empty string
- Propagate previous match for consecutive *
- Fill dp table:
- For '*': can match current char or skip it
- For '?' or matching char: check previous match
- For non-matching char: false
Key points:
- Uses 2D dp table for matching
- Handles both * and ? wildcards
- Considers empty string cases
- Matches entire string, not partial