-
Notifications
You must be signed in to change notification settings - Fork 0
/
0010_Regular_Expression_Matching.cs
63 lines (61 loc) · 1.91 KB
/
0010_Regular_Expression_Matching.cs
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
public class Solution {
public bool IsMatch(string s, string p) {
s = '@' + s;
p = '@' + p;
int ns = s.Length;
int np = p.Length;
bool [,] mt = new bool[ns, np];
mt[0, 0] = true;
for (int si = 1; si < ns; si++) mt[si, 0] = false;
for (int pi = 1; pi < np; pi++)
{
for (int si = 0; si < ns; si++)
{
if (char.IsLetter(p[pi])) {
if (si == 0)
{
mt[si, pi] = false;
continue;
}
mt[si, pi] = si > 0 && s[si] == p[pi] && mt[si-1, pi-1];
continue;
}
if (p[pi] == '.') {
if (si == 0) {
mt[si, pi] = false;
continue;
}
mt[si, pi] = mt[si-1, pi-1];
continue;
}
if (p[pi] == '*') {
if (mt[si, pi-2]) {
mt[si, pi] = true;
continue;
}
if (p[pi-1] == '.' || p[pi-1] == s[si]) {
if (si > 0 && mt[si-1, pi]) {
mt[si, pi] = true;
continue;
}
mt[si, pi] = false;
continue;
}
mt[si, pi] = false;
}
}
}
bool ret = mt[ns - 1, np - 1];
/*
Console.WriteLine($"%{s}");
for (int pi = 0; pi < np; pi++) {
Console.Write(p[pi]);
for (int si = 0; si < ns; si++) {
Console.Write(mt[si, pi] ? 1 : 0);
}
Console.WriteLine();
}
*/
return ret;
}
}