Leetcode#10 Regular Expression Matching

这道题坑了我很久，有一组测试数据在本地跑结果是true，但是在Leetcode服务器上跑结果就是false，让我百思不得其解。后来费了好久才终于找到原因，原来还是自己的代码不够严谨，为了让代码简洁一些，有一个判断语句默认空闲内存都是0，结果就错了。

这道题没有什么技巧，匹配的思路很直观，如果当前字符是*，直接跳过；如果不是*，该怎么处理要看下一个字符是不是*

1. 如果下一个字符不是*，那么这个字符必须能够被匹配，然后继续
2. 如果下一个字符是*，那么这个字符要匹配0，1，2，3...次，一直尝试下去

代码：

 1 bool matchp(const char *s, const char *p) {
 2   if (!*s) {
 3     while (*p && (*p == '*' || *(p + 1) == '*'))
 4       p++;
 5     return !*p;
 6   }
 7   else if (!*p)
 8     return false;
 9 
10   if (*p == '*')
11     return matchp(s, p + 1);
12 
13   if (*(p + 1) != '*')
14     return (*p == '.' || *s == *p) && matchp(s + 1, p + 1);
15   else {
16     do {
17       if (matchp(s, p + 2))
18         return true;
19       s++;
20     } while (*(s - 1) && (*p == '.' || *(s - 1) == *p));
21     return false;
22   }
23 }
24 
25 bool isMatch(const char *s, const char *p) {
26   if (!*p)
27     return !*s;
28 
29   return matchp(s, p);
30 }

虽然上面的代码已经可以AC了，但是耗时33ms，因为对于特定的匹配串效率很低，比如某个串包含好多a*b*c*...之类的，但最终结果是不能匹配，这个时候算法就会浪费大量时间递归回溯，可以小优化一下。

我的做法是先对正则串进行化简，然后再匹配。化简规则如下：

1. 相邻的多个*只保留一个
2. 对于X*Y*这种形式，如果X和Y都不是"."且X和Y相同，则只保留一个。例如，a*a*简化为a*
3. 对于X*Y*这种形式，如果X和Y任意一个为"."，则只保留"."。例如：a*.*或.*a*都可以简化成.*

比如一个匹配串是.*bc*.*b*b*a*.bc*，经过简化之后变成了.*b.*.bc*，效果还是很明显的。

优化后的代码：

 1 bool matchp(const char *s, const char *p) {
 2   if (!*s) {
 3     while (*p == '*' || *(p + 1) == '*')
 4       p++;
 5     return !*p;
 6   }
 7   else if (!*p)
 8     return false;
 9 
10   if (*p == '*')
11     return matchp(s, p + 1);
12 
13   if (*(p + 1) != '*')
14     return (*p == '.' || *s == *p) && matchp(s + 1, p + 1);
15   else {
16     do {
17       if (matchp(s, p + 2))
18         return true;
19       s++;
20     } while (*(s - 1) && (*p == '.' || *(s - 1) == *p));
21     return false;
22   }
23 }
24 
25 const char *simplify(const char *p) {
26   string reg;
27   char prev;
28 
29   reg.push_back(*p);
30   prev = *p;
31   for (p++; *p; p++) {
32     if (reg.back() == '*') {
33       if (*p == '*')
34         continue;
35       if (*(p + 1) == '*') {
36         if (*p == '.') {
37           while (reg.back() == '*') {
38             reg.pop_back();
39             reg.pop_back();
40           }
41           prev = *p;
42           reg.push_back(*p);
43         }
44         else if (prev != '.' && *p != prev) {
45           prev = *p;
46           reg.push_back(*p);
47         }
48       }
49       else {
50         prev = *p;
51         reg.push_back(*p);
52       }
53     }
54     else {
55       reg.push_back(*p);
56       if (*p != '*')
57         prev = *p;
58     }
59   }
60 
61   char *res = new char[reg.length()];
62   strcpy(res, reg.c_str());
63 
64   return res;
65 }
66 
67 bool isMatch(const char *s, const char *p) {
68   if (!*p)
69     return !*s;
70 
71   simplify(p); // new
72 
73   return matchp(s, p);
74 }

优化后耗时9ms