1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        const char *tmp = p;
        int cnt = 0;
        while (*tmp != '\0') if (*(tmp++) != '*') cnt++;
        if (cnt > strlen(s)) return false;

        if(strlen(s) == 0) {
            for(int i = 0;i < strlen(p);i++) {
                if(p[i] != '*')return false;
            }
            return true;
        }

        int **dp;
        dp = new int*[strlen(s) + 1];
        for(int i = 0; i <= strlen(s); i++) {
            dp[i] = new int[strlen(p) + 1];
        }
        dp[0][0] = 1;
        int i = 0;
        while(p[i++] == '*') dp[0][i] = 1;
        for(int i = 1; i <= strlen(s); i++) {
            for(int j = 1; j <= strlen(p); j++) {
                if(dp[i-1][j-1] == 1 && (s[i-1] == p[j-1] || p[j-1] == '?')) {
                    dp[i][j] = 1;
                }
                if(p[j-1] == '*' && (dp[i][j-1] == 1 || dp[i-1][j-1] == 1 || dp[i-1][j] == 1)) {
                    dp[i][j] = 1;
                }
            }
        }
        if(dp[strlen(s)][strlen(p)] == 1) return true;
        else
            return false;
    }
};