Algorithm/LeetCode/isMatch.cpp at master · feelpython/Algorithm · GitHub

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > mm;
string strs, strp;
int lens, lenp;

int isok(int idxs, int idxp) {
    int& ret = mm[idxs][idxp];
    if (ret != -1) return ret;
    ret = 0;
    if (idxp == lenp) {
        if (idxs == lens) return ret = 1;
        else return ret;
    }
    if (strp[idxp] == '.') {
        if (idxp + 1 < lenp && strp[idxp + 1] == '*') {
            for (int i = idxs; i <= lens; ++i) {
                if (isok(i, idxp + 2)) {
                    return ret = 1;
                }
            }
        } else if (idxs < lens && isok(idxs + 1, idxp + 1)) {
            return ret = 1;
        }
    } else {
        if (idxp + 1 < lenp && strp[idxp + 1] == '*') {
            if (isok(idxs, idxp + 2)) {
                return ret = 1;
            }
            for (int i = idxs; i < lens; ++i) {
                if (strs[i] != strp[idxp]) break;
                if (isok(i + 1, idxp + 2)) {
                    return ret = 1;
                }
            }
        } else if (idxs < lens && strs[idxs] == strp[idxp] && isok(idxs + 1, idxp + 1)) {
            return ret = 1;
        }
    }
    return ret;
}

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        strs = string(s);
        strp = string(p);
        lens = strs.length();
        lenp = strp.length();
        mm.clear();
        mm.resize(lens + 5, vector<int>(lenp + 5, -1));
        return isok(0, 0) == 1;
    }
};

int main() {
    Solution s = Solution();
    cout << s.isMatch("aa", "a") << endl;
    cout << s.isMatch("aa", "aa") << endl;
    cout << s.isMatch("aaa", "aa") << endl;
    cout << s.isMatch("aa", "a*") << endl;
    cout << s.isMatch("aa", ".*") << endl;
    cout << s.isMatch("ab", ".*") << endl;
    cout << s.isMatch("aab", "c*a*b") << endl;
    return 0;
}