forked from leetcoders/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
RegularExpressionMatching.h
77 lines (70 loc) · 2.51 KB
/
RegularExpressionMatching.h
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
77
/*
Author: Annie Kim, [email protected]
Co-author: King, [email protected]
Date: May 26, 2013
Update: Oct 26, 2014
Problem: Regular Expression Matching
Difficulty: Hard
Source: http://leetcode.com/onlinejudge#question_10
Notes:
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true
Solution: Both of the two solutions are from http://leetcode.com/2011/09/regular-expression-matching.html .
Solution 3: DP.
*/
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
if (*(p+1) == '*') // next is '*'
{
while ((*s == *p || *p == '.') && *s != '\0')
{
if (isMatch(s, p+2))
return true;
s++;
}
return isMatch(s, p+2);
}
if (*s == '\0') return false;
return (*s == *p || *p == '.') && isMatch(s+1, p+1);
}
bool isMatch_2(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
if (*s == *p || *p == '.' && *s != '\0')
return *(p+1) != '*' ? isMatch(s+1, p+1) :
isMatch(s+1, p) || isMatch(s, p+2);
else
return *(p+1) == '*' && isMatch(s, p+2);
}
bool isMatch_3(const char *s, const char *p) {
int l1 = strlen(s), l2 = strlen(p), k;
char ch1, ch2;
vector<vector<bool> > f(l1 + 1, vector<bool>(l2 + 1,false));
f[0][0] = true;
for (int i = 2; i <= l2; i ++)
if (*(p + i - 1) == '*') f[0][i] = f[0][i - 2];
for (int i = 1; i <= l1; i ++)
for (int j = 1; j <= l2; j ++) {
ch1 = *(s + i - 1); ch2 = *(p + j - 1);
if (ch2 != '*') f[i][j] = f[i - 1][j - 1] && (ch1 == ch2 || ch2 == '.');
else {
f[i][j] = f[i][j - 2];
if (*(s + i - 1) == *(p + j - 2) || *(p + j - 2) == '.') f[i][j] = f[i][j] | f[i - 1][j];
}
}
return f[l1][l2];
}
};