遇到一个有意思的题，分享出来一起看看。
零、背景
作为一个合格的程序员，日常工作中使用正则表达式应该是常态。
那你有没有想过正则表达式是如何实现的呢？
刚好，leetcode 上有一个简化版的正则表达式题目，我们来看看吧。
一、题意
给一个正则表达式，由小写字母、*
、?
组成。
*
代表匹配任意字符串，包括空字符串。?
代表匹配任意一个字符。
问正则表达式是否匹配输入的纯小写字母字符串。
二、基本做法
我们不去管正则表达式，就按题目的要求去作者道题的话，会发现这是一个动态规划题。
比如从前到后看，可以定义函数f(l, r)
代表判断以l
位置开始的字符串是否与以r
位置开始的正则表达式。
其中入口是f(0, 0)
。
这里有很多状态转移和出口。
1、l
和r
都结束，则匹配
2、l
未结束，r
结束，则不匹配
3、l
结束，r
未结束，若r
后面全为*
时匹配，否则不匹配。
4、如果l
与r
相等或者r
是为?
，则判断f(l+1, r+1)
5、如果r
不为*
，则不匹配。
6、此时r
是*
，如果r
是最后一个字符，则匹配。
7、依次假设*
的长度为x=0~MAX
，检查f(l+x, r+1)
，只要一个匹配则算匹配。
8、否则当前函数不匹配。
复杂度：O(nm)
其中n
是字符串的长度，m
是正则的长度。
由于正则一般不会很长，这个算法还可以接受。
四、优化
可以发现，当正则匹配时，其实速度很快，马上结束了流程。
而不匹配的时候，需要回溯继续匹配，这导致最终复杂度是O(nm)
可以发现，正则里是字母或者?
时，不需要回溯，只需要判断f(l+1,r+1)
。
正则是*
时，需要寻找子串，才产生O(nm)
的复杂度。
如果我们可以减少*
的话，回溯次数就会减少。
比如连续的*
按一个处理，这些都是初级的优化。
这里还有一个高级的优化，可以大大降低不匹配时的均摊复杂度。
比如对于输入串是S0 S1 S0 S1 S3
，正则是* S1 * S2
。
最终结果是不匹配。
匹配到第一个S1
后，会判断f(S0 S1 S3, * S2)
，然后得出结果不匹配。
匹配到第二个S1
后，会判断f(S3, * S2)
，最终得出的还是不匹配。
其实匹配第一个S1
后结果是不匹配，则可以确定整个串不匹配了。
这样计算量直接减少一半，如果*
多了，可以减少大量的不必要的判断。
那为什么可以确定后面肯定不匹配呢。
这里可以使用反证法。
假设第一个不匹配，第二个匹配，即第二个S1
后，f(S3, * S2)
匹配。
由于S0 S1 S3
和S3
相比，只是多了一个前缀，这个前缀可以用* S2
的*
来消除。
因此f(S0 S1 S3, * S2)
也是匹配的。
假设不成立，所以之后肯定不会匹配。
由此，可以愉快的使用这个优化了。
代码如下，只需要记录上次 * 的位置，只向上回溯一次。
五、最后
好了，初级的正则表达式就介绍到这里了。
这里主要分析了基本的动态规划方法，还介绍了多个*
时的一个不错的剪枝策略。
剪枝策略你看懂了吗？
关于进一步优化，你是不是想到了KMP
呢？
有什么思路吗？
PS：后台回复 "leetcode-wildcard-matching" 获取这两个方法的源码。
-EOF-
题图：来源自朋友圈。
上篇文章：Leetcode 第 16 场双周赛回顾
本文公众号：天空的代码世界
个人微信号：tiankonguse
微博：tiankongus
twitter：tiankonguse
微信群：微信拉你（算法闲聊群）
QQ算法群：165531769（比赛通知群）
知识星球：不止算法
