[LeetCode] Regular Expression Matching

题意

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

题解

第一次尝试

只支持 . 和 *…… 不就是是正则么，直接交上去个正则行不行？

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

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

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

这时为什么呢？我们来验证一下：

a = '^\\[abc\\]\\+$'
a #'^\\[abc\\]\\+$'
print(a) #^\[abc\]\+$

这个现象正式症结所在。

代码

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        import re
        # 其实下面这个 for 有问题，并不能起效果
        # for ch in "[]{}()+-^$|?,:\\":
        #    p = p.replace(ch, "\\" + ch)
        return re.match('^' + p + '$', s) is not None

结果

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

看来是可以的……

第二次尝试

正在写啦，别急。

桩程序

if __name__ == '__main__':
    cases = [
        {'x': 'aa', 'y': 'a', 'ans': False},
        {'x': 'aa', 'y': 'aa', 'ans': True},
        {'x': 'aaa', 'y': 'aa', 'ans': False},
        {'x': 'aa', 'y': 'a*', 'ans': True},
        {'x': 'aa', 'y': '.*', 'ans': True},
        {'x': 'ab', 'y': '.*', 'ans': True},
        {'x': 'aab', 'y': 'c*a*b', 'ans': True},
        {'x': 'adefffghi', 'y': '[abc]+def*.gh*i', 'ans': False},
        {'x': '[abc]+', 'y': '[abc]+', 'ans': True},
    ]

    for item in cases:
        ans = (Solution()).isMatch(s=item['x'], p=item['y'])
        print(str(ans == item['ans']) + "\t=>" + str(ans) + ":" + str(item['ans']))