[LeetCode] Regular Expression Matching

题意

写一个只支持 .* 的正则表达式匹配器。

题解

第一次尝试

只支持 .*…… 不就是是正则么,直接交上去个正则行不行?

尽量把正则的元素都去掉,只保留 .*。但是写了好久,脱字符的问题一直搞不定。直接交上去碰碰运气,竟然过了。

脱字符怎么了呢?比如我有一个 [abc]+def*.gh*i 正则式子,想去匹配 adefffghi。注意正则式子里面只支持 .*。所以,这个匹配应该是返回 False 的。一个更极端的例子,拿 [abc]+ 去匹配 [abc]+ 应该也是 True 的。

但是我们来看看按照下面的代码处理出来的正则串。对于第一个例子,处理后的正则表达式是 ^\\[abc\\]\\+def*.gh*i$;对于第二个例子,处理后的正则表达式是 ^\\[abc\\]\\+$。我们发现本应该是 \char 的地方全部变成了 \\char,在表面上看来是我们想要的,因为如果手动在代码里面输入这些东西去匹配,得到的结果都是 True。但是用处理后的正则式子进行 compile 和 mach 却是出错的。

这时为什么呢?我们来验证一下:

这个现象正式症结所在。

代码

结果

445 / 445 test cases passed.
Status: Accepted
Runtime: 158 ms

看来是可以的……

第二次尝试

正在写啦,别急。

桩程序

发表评论

电子邮件地址不会被公开。 必填项已用*标注