Algorithm
Problem Name: 44. Wildcard Matching
Problem Link: https://leetcode.com/problems/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).
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'.
Constraints:
0 <= s.length, p.length <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define MATCH(A, B) ((A) == (B) || ((A) && (B) == '?'))
#define IDX(I, J) ((I + 1) * (plen + 1) + J + 1)
#define ALG 1
bool match_recursive(char *s, char *p, int *retry) {
if (!*p) return (*s) ? 0 : 1;
if (*p == '*') {
do { p ++; } while (*p == '*');
if (!*p) return 1;
while (*s && *retry) {
if (match_recursive(s, p, retry)) {
return 1;
}
s ++; // skip one and retry
}
*retry = 0; // s reaches the end, still not matching, no need to retry on all previous '*'
return 0;
}
if (!MATCH(*s, *p)) return 0;
return match_recursive(s + 1, p + 1, retry);
}
bool match_2_pointers(char *s, char *p) {
char *saved_s, *saved_p = NULL;
while (*s) {
if (*p == '*') {
do { p ++; } while (*p == '*');
if (!*p) return 1;
saved_s = s + 1; // save the next s pointer for retry with skipping one
saved_p = p; // save the next p pointer for retry with skipping one
continue;
}
if (MATCH(*s, *p)) { s ++; p ++; continue; }
if (saved_p) {
s = saved_s ++; // go back to previously saved s pointer
// and advance the saved pointer for continuously skipping one
p = saved_p; // go back to previously saved p pointer and retry
continue;
}
return 0;
}
while (*p == '*') p ++;
return (*p) ? 0 : 1;
}
bool match_dp(char *s, char *p) {
int slen = strlen(s);
int plen = strlen(p);
int *dp = calloc((slen + 1) * (plen + 1), sizeof(int));
int i, j;
dp[0] = 1;
for (j = 0; j < plen; j ++) {
if (p[j] == '*') {
dp[IDX(-1, j)] = dp[IDX(-1, j - 1)];
}
}
for (i = 0; i < slen; i ++) {
for (j = 0; j < plen; j ++) {
if (p[j] != '*') {
// it is a match if current match and previous s & p are a match
dp[IDX(i, j)] = MATCH(s[i], p[j]) && dp[IDX(i - 1, j - 1)];
} else {
dp[IDX(i, j)] = dp[IDX(i, j - 1)] || // '*' match empty
dp[IDX(i - 1, j)]; // '*' match as one or multiple of any
}
}
}
i = dp[IDX(slen - 1, plen - 1)];
free(dp);
return i;
}
bool isMatch(char* s, char* p) {
#if ALG == 1 // 8ms, 7M
int retry = 1;
return match_recursive(s, p, &retry);
#elif ALG == 2 // 8ms, 7M
return match_2_pointers(s, p);
#else // 48ms, 23M
return match_dp(s, p);
#endif
}
Input
s = "aa", p = "a"
Output
false
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool isMatch(string s, string p) {
if(p.empty()) return s.empty();
if(s.empty()) return p.empty() || p[0] == '*' ? isMatch(s, p.substr(1)) : false;
if(p[0] != '?' && p[0] != '*' && p[0] != s[0]) return false;
if(p[0] == '*'){
for(int i = 0; i <= s.size(); i++)
if(isMatch(s.substr(i), p.substr(1))) return true;
return false;
}
return isMatch(s.substr(1), p.substr(1)>;
}
};
Input
s = "aa", p = "*"
Output
true
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
int sIdx = 0;
int pIdx = 0;
int startIdx = -1;
int sTempIdx = -1;
while (sIdx < sLen) {
if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))) {
sIdx++;
pIdx++;
} else if (pIdx < pLen && p.charAt(pIdx) == '*') {
startIdx = pIdx;
sTempIdx = sIdx;
pIdx++;
} else if (startIdx == -1) {
return false;
} else {
pIdx = startIdx + 1;
sIdx = sTempIdx + 1;
sTempIdx = sIdx;
}
}
for (int i = pIdx; i < pLen; i++) {
if (p.charAt(i) != '*') {
return false;
}
}
return true;
}
}
Input
s = "cb", p = "?a"
Output
false
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const isMatch = function(s, p) {
const M = s.length
const N = p.length
let i = 0,
j = 0,
lastMatchInS,
lastStarPos
while (i < M) {
if (j < N && (p[j] === s[i] || p[j] === '?')) {
i++
j++
} else if (j < N && p[j] === '*') {
lastStarPos = j
j++
lastMatchInS = i
} else if (lastStarPos !== undefined) {
// back to previous step
j = lastStarPos + 1
lastMatchInS++
i = lastMatchInS
} else {
return false
}
}
while (j < N && p[j] === '*') {
j++
}
return j === N
}
Input
s = "aa", p = "a"
Output
false
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isMatch(self, s, p):
sp = pp = match = 0
star = -1
while sp < len(s):
if (pp < len(p) and (s[sp] == p[pp] or p[pp] == '?')):
sp +=1
pp +=1
elif pp < len(p) and p[pp] == '*':
star = pp
match = sp
pp +=1
elif star != -1:
pp = star + 1
match +=1
sp = match
else:
return False
while(pp < len(p) and p[pp] == '*'):
pp += 1
return pp == len(p)
Input
s = "aa", p = "*"
Output
true
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _044_WildcardMatching
{
public bool IsMatch(string s, string p)
{
int sIndex = 0, pIndex = 0;
int lastSIndex = -1, lastPIndex = -1;
while (sIndex < s.Length)
{
if (pIndex < p.Length && (p[pIndex] == '?' || p[pIndex] == s[sIndex]))
{
sIndex++;
pIndex++;
}
else if (pIndex < p.Length && p[pIndex] == '*')
{
pIndex++;
if (pIndex == p.Length) { return true; }
lastSIndex = sIndex;
lastPIndex = pIndex;
}
else
{
if (lastSIndex == -1) { return false; }
sIndex = ++lastSIndex;
pIndex = lastPIndex;
}
}
while (pIndex < p.Length && p[pIndex] == '*') { pIndex++; }
return pIndex == p.Length && sIndex == s.Length;
}
}
}
Input
s = "cb", p = "?a"
Output
false