Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") â…

leetcode_wildcard_matching.cpp

#define MAXN 500
int f[MAXN][MAXN];

bool isMatch_(const char* s, const char* p, int n, int m) {
    if (n < 0 && m < 0)
        return true;
    else if (n >= 0 && m < 0)
        return false;
    else if (n < 0) {
        for (int i = 0; i <= m; ++i)
            if (p[i] != '*')
                return false;
        return true;
    }
    if (f[n][m] != -1)
        return f[n][m];
    if (s[n] == p[m] && isMatch_(s, p, n - 1, m - 1))
        return f[n][m] = 1;
    if (p[m] == '?' && isMatch_(s, p, n - 1, m - 1))
        return f[n][m] = 1;
    if (p[m] == '*' && (isMatch_(s, p, n - 1, m) || isMatch_(s, p, n, m - 1)))
        return f[n][m] = 1;
    return f[n][m] = 0;
}

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int n = strlen(s);
        int m = strlen(p);
        memset(f, -1, sizeof(f));
        return isMatch_(s, p, n - 1, m - 1);
    }
};