# Wildcard Matching Leetcode Solution

In this post, we are going to solve the Wildcard Matching Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## Problem

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 `'*'`.

Now, lets see the leetcode solution of Wildcard Matching Leetcode Solution.

### Wildcard Matching Leetcode Solution in Python

```class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s)
n = len(p)
# dp[i][j] := True if s[0..i) matches p[0..j)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True

def isMatch(i: int, j: int) -> bool:
return i >= 0 and p[j] == '?' or s[i] == p[j]

for j, c in enumerate(p):
if c == '*':
dp[0][j + 1] = dp[0][j]

for i in range(m):
for j in range(n):
if p[j] == '*':
matchEmpty = dp[i + 1][j]
matchSome = dp[i][j + 1]
dp[i + 1][j + 1] = matchEmpty or matchSome
elif isMatch(i, j):
dp[i + 1][j + 1] = dp[i][j]

return dp[m][n]
```

### Wildcard MatchingLeetcode Solutionin CPP

```class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length();
const int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp[0][0] = true;

auto isMatch = [&](int i, int j) -> bool {
return j >= 0 && p[j] == '?' || s[i] == p[j];
};

for (int j = 0; j < p.length(); ++j)
if (p[j] == '*')
dp[0][j + 1] = dp[0][j];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p[j] == '*') {
const bool matchEmpty = dp[i + 1][j];
const bool matchSome = dp[i][j + 1];
dp[i + 1][j + 1] = matchEmpty || matchSome;
} else if (isMatch(i, j)) {
dp[i + 1][j + 1] = dp[i][j];
}

return dp[m][n];
}
};
```

### Wildcard Matching Leetcode Solution in Java

```class Solution {
public boolean isMatch(String s, String p) {
final int m = s.length();
final int n = p.length();
// dp[i][j] := true if s[0..i) matches p[0..j)
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;

for (int j = 0; j < p.length(); ++j)
if (p.charAt(j) == '*')
dp[0][j + 1] = dp[0][j];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p.charAt(j) == '*') {
final boolean matchEmpty = dp[i + 1][j];
final boolean matchSome = dp[i][j + 1];
dp[i + 1][j + 1] = matchEmpty || matchSome;
} else if (isMatch(s, i, p, j)) {
dp[i + 1][j + 1] = dp[i][j];
}

return dp[m][n];
}

private boolean isMatch(final String s, int i, final String p, int j) {
return j >= 0 && p.charAt(j) == '?' || s.charAt(i) == p.charAt(j);
}
}
```

Note: This problem Wildcard Matching is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

Sharing Is Caring