# Wildcard Matching Problem Solution

Wildcard Matching 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 :

```Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".```

## Problem Solution In Python

``````class Solution(object):
def isMatch(self, s, p):
dp = [[False for i in range(len(p)+1)] for j in range(len(s)+1)]
dp[0][0] = True

s = "#" + s
p = "#" + p

for j in range(1, len(dp[0])):
if p[j] == "*":
dp[0][j] = dp[0][j-1]

for i in range(1, len(dp)):
for j in range(1, len(dp[0])):
if s[i] == p[j] or p[j] == "?":
dp[i][j] = dp[i-1][j-1]
elif p[j] == "*":
dp[i][j] = (dp[i-1][j-1] or dp[i][j-1] or dp[i-1][j])

return dp[-1][-1]
``````

## Problem Solution In Java

``````class Solution {
public boolean isMatch(String s, String p) {
Boolean[][] dp = new Boolean[s.length()][p.length()];
return match(s, p, 0, 0, dp);
}

public boolean match(String s, String p, int i, int j, Boolean[][] dp) {
if(i >= s.length() && j >= p.length()) {
return true;
}
if(i >= s.length() && p.charAt(j) == '*') {
return match(s, p, i, j+1, dp);
}
if(i >= s.length()) {
return false;
}
if(j >= p.length()) {
return false;
}
if(dp[i][j] != null) return dp[i][j];
if(p.charAt(j) == '*') {
dp[i][j] = match(s, p, i+1, j+1, dp) || match(s, p, i+1, j, dp) || match(s, p, i, j+1, dp);
} else if(p.charAt(j) == s.charAt(i)) {
dp[i][j] = match(s, p, i+1, j+1, dp);
} else if(p.charAt(j) == '?'){
dp[i][j] = match(s, p, i+1, j+1, dp);
}else{
dp[i][j] = false;
}
return dp[i][j];
}
}
``````

## Problem Solution In C++

``````class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size();
int m = p.size();

vector<vector<bool>> dp(m+1,vector<bool>(n+1));

for(int i = 0; i <= m; i++){
for(int j = 0; j <= n; j++){

if(i == 0 and j == 0)
dp[i][j] = true;

else if(i == 0)
dp[i][j] = false;

else if(j == 0) {
if(p[i-1] == '*')
dp[i][j] = dp[i-1][j];

else dp[i][j] = false;
}
else {

if(p[i-1] == s[j-1])
dp[i][j] = dp[i-1][j-1];

else if(p[i-1] == '?')
dp[i][j] = dp[i-1][j-1];

else if(p[i-1] == '*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
else {
dp[i][j] = false;
}
}
}
}
return dp[m][n];
}
};
``````

## Problem Solution In C

``````bool isMatch(char * s, char * p)
{
int len_s = strlen(s);
int len_p = strlen(p);

int t_rows = len_p + 1;
int t_cols = len_s + 1;
int t_len = t_rows * t_cols;

bool* table = (bool*)malloc(t_len * sizeof(bool));
memset(table, 0, t_len * sizeof(bool));

int pos = 0;

for (int i = 0; i < t_rows; i++) {
for (int j = 0; j < t_cols; j++) {
if (i == 0) {
if (j == 0) {
table[0] = true;
}
pos++;
continue;
}

if (p[i - 1] == '*') {
if (table[pos - t_cols] == true ||
(j > 0 && table[pos - 1] == true))
{
table[pos] = true;
}
} else if (p[i - 1] == '?') {
if (j > 0 && table[pos - t_cols - 1] == true)
{
table[pos] = true;
}
} else {
if (j > 0 && table[pos - t_cols - 1] == true &&
p[i - 1] == s[j - 1])
{
table[pos] = true;
}
}

pos++;
}
}

return table[pos - 1];
}``````