来源

对应leetCode第10题，难度级别：困难

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符

'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

举例：

输入:

s = "aa"

p = "a"

输出: false

解释: "a" 无法匹配 "aa" 整个字符串。

=======================

输入:

s = "aa"

p = "a*"

输出: true

解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

========================

输入:

s = "ab"

p = ".*"

输出: true

解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

========================

输入:

s = "aab"

p = "c*a*b"

输出: true

解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

解题思路

假如不考虑 . 和 * ，仅仅判断两个字符串是否匹配，一种比较简单的思路是两个指针分别指向字符串的头部，判断指向的元素是否相等，如果不想等，则直接返回false，相等的话则继续移动；

进阶，假如只考虑 . ,依然可以沿用上述思路，值是判断相等的时候如果正则对应的是 . 则无论另一个指针的字符是什么，均认为相等；

下面考虑 * 如何处理，根据题目描述，不能单独考虑* ，需要考虑*以及其前面一个字符；比如a* 表示，a可以出现零次或多次；

根据前面的思路，首先将正则分隔为列表，分隔原则是保证列表每个元素没有通配符或者只有通配符，比如：abc*de.acd.*ab 应该分割为：ab、c*、de、.、acd、.*、ab

分隔代码如下：

之后继续沿用双指针思路，如果正则列表指针指向的元素不包含通配符，那么直接比较与原串指针以及其后面的字符构成的长度相对应的串是否相等，如果不等，直接返回false，相等则移动指针；

如果遇见 . 则两个指针均移动一步即可；

如果意见 x*，这个时候假设x出现0次，则正则指针移动一步，另一个指针不移动；出现一次，则另一个指针移动1步... ... 直到另一个指针指向的元素不是x；

整体逻辑如下：