# Chef and the Wildcard Matching codechef solution in c++

```
#include <iostream>
#include <string>
using namespace std;
bool isMatch(string pattern, string str) {
int m = pattern.length(), n = str.length();
bool dp[m + 1][n + 1];
memset(dp, false, sizeof(dp));
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
if (pattern[i - 1] == '*')
dp[i][0] = dp[i - 1][0];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (pattern[i - 1] == '*')
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
else if (pattern[i - 1] == '?' || pattern[i - 1] == str[j - 1])
dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[m][n];
}
int main() {
string pattern, str;
cin >> pattern >> str;
bool result = isMatch(pattern, str);
if (result)
cout << "Yes, the pattern matches the string.";
else
cout << "No, the pattern does not match the string.";
return 0;
}
```

Explanation:

- The code defines a function
`isMatch`

that takes two strings`pattern`

and`str`

and checks if the pattern matches the string. - It initializes variables
`m`

and`n`

to store the lengths of`pattern`

and`str`

respectively. - A 2D boolean array
`dp`

is created with dimensions`(m+1) x (n+1)`

to store intermediate matching results. It is initialized with`false`

. `dp[0][0]`

is set to`true`

as an empty pattern matches an empty string.- The first
`for`

loop sets`dp[i][0]`

to`true`

for*characters in the pattern, as*can match an empty string or any sequence of characters. - The nested
`for`

loops iterate through each character in`pattern`

and`str`

, checking conditions to update the`dp`

array based on the matching rules: - If the current character in the pattern is
`*`

, it sets`dp[i][j]`

to`true`

if either the previous pattern character matches the current string character or the previous string character matches the current pattern character. - If the current pattern character is
`?`

or matches the current string character, it sets`dp[i][j]`

based on the previous matching status. - Finally, the function returns
`dp[m][n]`

, indicating whether the entire pattern matches the entire string. - In the
`main`

function, it reads input for`pattern`

and`str`

, calls the`isMatch`

function, and outputs whether the pattern matches the string or not.