[leetcode_10]Regular Expression Matching

搜索+剪枝，不过有一个很奇怪的地方就是一组测试数据过不了，加了一个针对测试数据的剪枝才AC的。所以，还是应该弄弄DP的方法。当时一直想用贪心，显然涉及到很多地方的回溯，贪心的方法不好使。另外注意a* 认为是一体的就是它代表空，多个a形成的串。

 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


class Solution {
public:
    bool result;
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        result = false;
        int lens = strlen(s);
        int lenp = strlen(p);
        if(p[lenp-1] != '*' && s[lens-1] != p[lenp-1] && p[lenp-1]!='.')return result;
        matchStep(s,p);
        return result;
    }
private:
    void matchStep(const char * s,const char * p) {
        if(result)return;
        if(*s == '\0' && *p == '\0') {
            result = true;
            return;
        }
        if(*s == '\0') {
            if(*(p+1) == '*') {
                matchStep(s,p+2);
                return ;
            }
        }
        if(*s == '\0' || *p == '\0')return;
        if(*(p+1) != '\0') {
            if(*(p+1) != '*') {
                if(*s == *p || *p == '.') {
                    matchStep(s+1,p+1);
                }
                else
                    return;
            }
            else {
                if(*s != *p && *p != '.') {
                    matchStep(s,p+2);
                }
                else {
                    matchStep(s,p+2);
                    matchStep(s+1,p);
                    matchStep(s+1,p+2);
                }
            }
        }
        else {
            if(*s == *p || *p == '.') {
                matchStep(s+1,p+1);
            }
            else
                return;
        }
    }
};