leetcode.cn 10.正则表达式匹配 记忆化搜索

心血来潮想刷刷题玩，想起leetcode，注册登录，知道leetcode上的题都比较简单，就勾选难度为“困难”，然后看到此题。

读完题，心想这标为“困难”，该不会是得用DFA甚至NFA吧？

又仔细看了下测试数据，数据量不大，直接搜索吧，暴搜如果超时，再考虑剪枝或者加记忆化。

花了二十多分钟敲完代码，交上去，果然TLE。不过，leetcode比OJ人性化啊，还告诉我超时前最后执行的是"aaaaaaaaaaaaab" "a*a*a*a*a*a*a*a*a*a*c"这组测试数据，于是我改进了下模式串的处理，再交，还是超时，不过已经不提示是哪组超时了，估计是所有测试数据运行的总时间超了吧。

没办法那还是加记忆化吧。也很简单，就是加个标记数组hasjudged，加几行代码把搜过的记录一下避免下次重复搜就行。再交，就过了。真简单，这种题在ACM/ICPC只能算水题吧。^_^

 1 int extend_pattern(string p, char* pstr) {
 2     int I = 0;
 3     for (int i = 0, n = p.size(); i < n; i++) {
 4         pstr[I++] = p[i];
 5         if (i + 1 < n && p[i + 1] == '*') {
 6             pstr[I++] = '*';
 7             i++;
 8         } else {
 9             pstr[I++] = '1';
10         }
11         // 合并模式串
12         if (I >= 4) {
13             // 暂时只合并这一种
14             if (pstr[I - 4] == pstr[I - 2] && pstr[I - 1] == '*' && pstr[I - 3] == '*') {
15                 I -= 2;
16             }
17         }
18     }
19     pstr[I] = 0;
20     //cout << pstr << endl;
21     return I;
22 }
23 
24 inline bool is_match(char a, char b) {
25     if (b == '.') {
26         return a != '\0';
27     }
28     return a == b;
29 }
30 
31 bool hasjudged[22][32];
32 
33 bool is_match(const char* str, int sn, const char* pstr, int pn) {
34     //cerr << sn << " " << pn << endl;
35     if (sn == 0 && pn == 0) {
36         return true;
37     }
38     if (pn == 0) {
39         return false;
40     }
41     if (hasjudged[sn][pn]) {
42         return false;
43     }
44     if (pstr[1] == '1') {
45         // 这里没有单独考虑str已经用完的情况，因为空字符跟其它字符不会匹配
46         if (!is_match(str[0], pstr[0])) {
47             hasjudged[sn][pn] = true;
48             return false;
49         }
50         bool ret = is_match(str + 1, sn - 1, pstr + 2, pn - 1);
51         hasjudged[sn][pn] = true;
52         return ret;
53     }
54     if (is_match(str, sn, pstr + 2, pn - 1)) {
55         return true;
56     }
57     for (int i = 0; i < sn; i++) {
58         if (!is_match(str[i], pstr[0])) {
59             break;
60         }
61         if (is_match(str + i + 1, sn - i - 1, pstr, pn)) {
62             return true;
63         }
64     }
65     hasjudged[sn][pn] = true;
66     return false;
67 }
68 
69 class Solution {
70 public:
71     bool isMatch(string s, string p) {
72         memset(hasjudged, 0, sizeof(hasjudged));
73         char pstr[80];
74         int pn = extend_pattern(p, pstr);
75         int sn = s.length();
76         return is_match(s.c_str(), sn, pstr, pn / 2);
77     }
78 };