10.Regular Expression Matching （

题目描述：

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

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个字符串 s 的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

代码：

class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern: return not text
        match_res = bool(text) and pattern[0] in {text[0], '.'} # 这里bool(text)的作用是为了保证后面的text[0]不会发生索引越界的情况（因为text有可能为空）
        
        if len(pattern) > 1 and pattern[1] == '*':
            return self.isMatch(text, pattern[2:]) or 
                   (match_res and self.isMatch(text[1:], pattern))
        else:
            return match_res and self.isMatch(text[1:], pattern[1:])

思路分析：

本题和《剑指offer》的第19题是一样的。如果 pattern 中没有 * ，则问题可以通过如下的递归来解决：

def match(text, pattern):
    if not pattern: return not text # 先写递归基
    match_res = bool(text) and pattern[0] in {text[0], '.'} # text只要不空，转化为bool均返回True
    return match_res and match(text[1:], pattern[1:])

当 * 出现时，前面一定会跟一个其他字符，所以每一次对 pattern 切片后，* 一定会出现在 pattern[1] 的位置。如何应对 * 出现时的情况呢？有如下两种解决方案：

• 其一，因为 * 代表它前面的字符可以出现 0 次，所以跳过 * 和它前面的那个字符，从 * 后面的字符开始重新对当前的 text[0] 进行匹配，即 match(text, pattern[2:])；
• 其二，因为 * 代表它前面的字符可以出现任意次，所以 * 和它前面的那个字符可以重复使用。如果当前这一轮 text[0] 和 pattern[0] 匹配成功，那么在下一轮递归时，text 要匹配的是 text[1:] ，而 pattern 则可以重复使用，不使用的情况已经在上面那一条说过了，重复使用的情况就是 pattern 不进行切片，仍然将当前 pattern 的全部内容传入下一轮递归中，即 match(text[1:], pattern) 。

可以看到，如果 pattern 中有 * ，则每一轮递归都有两条路可以选，而且在进入到下一轮递归后仍然有两条路可以选。

整个代码的思路是：

• 首先，不管哪种情况，由于 * 不可能出现在 pattern[0] 的位置，因此每次都要先判断第 0 个字符是否能匹配，判断的方法是：

  match_res = bool(text) and pattern[0] in {text[0], '.'}
  

• 当前 pattern 的长度大于 1 而且 pattern[1] == * 吗？

  • 如果上述条件满足，则又分为两条路：

    • match(text, pattern[2:])

    • match(text[1:], pattern)

      以上这两条路是并行执行的，而且只要有一条路满足就可以，所以要用 or 连接。

  • 如果上述条件不满足，就可以认为 pattern[0] 和 pattern[1] 里面均不包含 * （至少在当前 pattern 的前两个位置是没有 * 的，后面的位置有 * 的情况先不管。因为代码是递归进行的，所以后面的位置如果有 * ，早晚有一天这个 * 肯定会挪到 pattern[1] 的位置，到那时再对它进行处理也不迟。）。那么这种情况退化为最开始的那种没有 * 的情况，此时在进行下一轮递归时，text 和 pattern 都要往后挪一位，即 match(text[1:], pattern[1:]) 。

在代码中，or 之前的那个分支之所以没有加上对 match_res 的判断，是因为可能会出现下面这种情况：

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