Regular Expression Matching (Leetcode hard algorithm problem)

经过上周的medium热身之后，这周决定选个hard的来训练一下。 这次题目为正则表达式，描述如下。原题链接

‘.’ 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

在以前学习CS的时候，老师最爱说的一句话是，当一个问题来临的时候，先去尝试最粗暴直接去解决它，如果这个直接方法效率太差，再去想办法去优化，解决问题先放在第一位。 于是，我使用了穷尽的方法……

不难看出来，正则表达式每一次匹配最多会有三种情况： Type 1.正则表达式向后偏移 （例子：a* 比配 b，此时之后正则表达式向后一位） Type 2.字符串向后偏移（例子：a*匹配 a，此时字符串匹配成功，向后一位，正则表达式可不便宜） Type 3.正则表达式和字符串都向后偏移（a匹配a，成功匹配，二者都向后偏移）

那么每一次匹配都是一颗三叉树，只要把这三叉树遍历完全，就会有答案。

结点的操作为： 1.当正则表达式和字符串都匹配到最尽头，返回成功。 2.如果能够按照上述三个条件生成出子节点的，加入子节点，然后遍历子节点。 3.如果既不成功，也不能生成子节点的，就返回失败。

既然是一棵树，那么就很明了了，直接上递归。 递归伪代码：

跑出来结果，是对的，只是额……超时了。 上诉递归是有问题的，看起来像是深度优先，但是跑起来是完全遍历。 应该是这样才对。

再次提交，还是超时，超时的例子在于 a*a*a*a*a*a*c 和 ab的匹配，这个是匹配不成功的的样例，因此，无论是深度优先还是广度优先，都需要把树完全遍历一遍，这样显然是很慢的。

不过我选择的并不是再在递归上去做优化，而是对正则表达式做优化。 因为 a*a*a*a*a*a*c = a*c 同类的，还有： .a*b*c*d=.* a*a*aaaaaa*= a*aaaa

好了，做完优化后，提交成功了，中规中矩。

最后附上C++代码