forked from fanfank/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
regular-expression-matching.cpp
76 lines (75 loc) · 2.24 KB
/
regular-expression-matching.cpp
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
69
70
71
72
73
74
75
76
/*****************************
Solution 1: very ugly codes
*****************************/
class Solution {
public:
struct node {
const char *spos, *ppos;
node(const char *sp, const char *pp) : spos(sp), ppos(pp) {}
};
bool isMatch(const char *s, const char *p) {
stack<node> sta;
bool f = false;
while(true) {
if(*s == 0 && *p == 0) {
f = true;
break;
}
if(*p && *(p+1) == '*') {
if(*s)
sta.push(node(s, p));
p = p + 2;
} else {
bool solved = true;
while(*s == '\0' || (*p != '.' && *p != *s)) {
solved = false;
if(sta.empty())
break;
node tmp = sta.top();
sta.pop();
s = tmp.spos;
p = tmp.ppos + 1;
if(*(tmp.ppos) == '.' || *(tmp.spos) == *(tmp.ppos)) {
if(*(tmp.spos + 1))
sta.push(node(tmp.spos + 1, tmp.ppos));
solved = true;
break;
}
}
if(solved) {
++s, ++p;
} else {
break;
}
}
}
return f;
}
};
/************************************************************
Solution 2: recursion method, good one. from iphkwan@github
************************************************************/
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (*p == '\0') {
return (*s == '\0');
}
if (*(p + 1) == '*') {
while ((*p == '.' && *s != '\0') || *s == *p) {
if (isMatch(s, p + 2)) {
return true;
}
s++;
}
return isMatch(s, p + 2);
} else {
if ((*p == '.' && *s != '\0') || *s == *p) {
return isMatch(s + 1, p + 1);
}
return false;
}
}
};