Leetcode/10RegularExpressionMatching_Recursion.cpp at master · EveWu/Leetcode · 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
class Solution {
public:
    bool isMatch(string s, string p) {
        return recursive(s, p, s.size(), p.size());
    }
    bool recursive(string s, string p, int slen, int plen) {
        int i = slen - 1, j = plen - 1;
        if (slen == 0) {
            if (plen == 0) {
                return true;
            } else if (plen == 1) {
                if (p[j] == '*') return true;
                else return false;
            } else {
                if (p[j] == '*') {
                    if (p[j-1] == '*') return recursive(s, p, slen, plen-1);
                    else return recursive(s, p, slen, plen-2);
                }
                else {
                    return false;
                }
            }
        } else {
            if (plen == 0) return false;
            else if (plen == 1) {
                if (s[i] == p[j] || p[j] == '.') {
                    return recursive(s, p, slen-1, plen-1);
                } else {
                    return false;
                }
            } else {
                if (s[i] == p[j] || p[j] == '.') {
                    return recursive(s, p, slen-1, plen-1);
                } else if (p[j] == '*') {
                    // set to 0
                    if (p[j-1] != s[i] && p[j-1] != '.') {
                        return recursive(s, p, slen, plen-2);
                    } else {
                        return recursive(s, p, slen-1, plen) || recursive(s, p, slen-1, plen-2) || recursive(s, p, slen, plen-2);
                    }
                } else {
                    return false;
                }
            }
        }
    }
};