每天一道算法：实现正则匹配

11、实现正则匹配

题目

给定一个输入字符串 s 和一个模式字符串 p ，实现正则匹配，支持 . 和 *，要求：

(1) . 可以匹配任意单个字符。

(2) * 可以匹配0个或多个前一个元素。

(3) 匹配需要覆盖整个输入字符串，而非部分匹配。

备注：

s 可以为空，且只会包含小写字母 a-z

p 可以为空，且只会包含小写字母 a-z，以及 . 或者 *

示例1：

示例2：

示例3：

示例4：

示例5：

思路

本题可以使用递归法，从左到右依次匹配。

如果 s 和 p 的第一位都是字母，或者 p 的第一位是 .，则说明第一位可以匹配上，然后s 和 p 的指针各+1，看剩下的字符串是否可以匹配上即可。

但是有一个特殊情况，就是如果 p 的第二位是 *，那么如果第一位可以匹配上，只需要将 s 的指针+1继续匹配，因为如果 s 的前 n 位都是相同的字符也都可以匹配上， p 的指针就不应该向前+1，这时候是 * 代表了n个前一个元素。直至第一位匹配不上了，这时候也不要直接返回 False，还需要将 p 的前两位跳过，继续匹配，这时候是 * 代表了0个前一个元素。

改进：

可以将上述过程中的每次子字符串的匹配结果，专门用一个词典存储起来，这样之后再次用到的话，直接取出即可，不必再计算一边。

为什么有可能再次用到？关键在于上面说的特殊情况，即 p 的第二位是 * 的情况。这时候第一位匹配上了，需要s指针+1，匹配不上的话，需要 p 指针+1，两者是 or 的关系，都需要计算出结果，这时候就可能会重复利用了。

代码

python实现