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.