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

class Solution {
public:
    bool matches(string s, string p, int i, int j) {
        if (i == 0) return false;

        if (p[j - 1] == '.') return true;

        return s[i - 1] == p[j - 1];
    }

    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();

        vector<vector<int>> f(m +1, vector<int>(n +1));
        f[0][0] = true;
        for (int i = 0; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] |= f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
};