## Algorithm

Problem Name: 44. 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 <= 2000`
• `s` contains only lowercase English letters.
• `p` contains 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
}
``````
Copy The Code &

Input

cmd
s = "aa", p = "a"

Output

cmd
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)>;
}
};
``````
Copy The Code &

Input

cmd
s = "aa", p = "*"

Output

cmd
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;
}
}
``````
Copy The Code &

Input

cmd
s = "cb", p = "?a"

Output

cmd
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
}
``````
Copy The Code &

Input

cmd
s = "aa", p = "a"

Output

cmd
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)
``````
Copy The Code &

Input

cmd
s = "aa", p = "*"

Output

cmd
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;
}
}
}
``````
Copy The Code &

Input

cmd
s = "cb", p = "?a"

Output

cmd
false