1.题目

原题

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

例子

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

2.解析

这道题是一道正则题，要求的是完全匹配而非部分匹配，思路有三种。

• python正则包
  python的优势在于有各种包可以直接调用，语句比较优雅，我们可以直接调用re包。
  这里边的知识点是re.findall和re.match这两个函数的用法。
  其中，findall是找到所有匹配，第一个匹配是满足条件的最常字符串，如果不加开始和结束符号的话，只要有局部匹配，就会输出全局字符串。match也一样只不过会按group输出，此为正则表达式的知识，有很多细节需要注意。
• 递归求解
  题意说的是，字符串和正则要完全匹配才能输出最终的结果，基本的思路应该是一个一个字符串去判断是否是匹配，如果没有特殊符号，这道问题就非常简单了，现在定义了两个特殊字符，主要要实现他们的功能。
  .匹配任意字符，当做一个判断条件，就是任意字符串都可以和.相同，只要正则字符串中出现.逻辑语句就返回True。
  匹配前面字符0次或多次，难点在于可以不匹配。需要分情况讨论，将放在正则字符串的第二个位置，如果匹配到了号，则分情况讨论，因为可以不匹配，那么会产生很多种情况。
  整体思路可以这么来理解：
  1）递归的程序出口是待匹配字符串p和正则表达式s，有一个为空。
  定义一个出口：如果p为空，则s必须为空，才能返回True，否则返回False。
  2）递归每次都需要做判断，实际就是逐个字符的比较，即待匹配字符串p和正则表达式s，第一个字符串是否相同，如果相同则继续递归判断，这个需要定义一个头部字符串是否相同的变量。
  len(p) > 1 and s[0] == p[0] or p[0] == '.'
  3)这一步是最重要的，分情况来说：
  判断条件是第二个字符串是否是*
  如果是：
  判断第一个字符串是不是相同，如果相同则匹配成功，将p右移一位和s继续匹配；如果第一个字符串不同，但是*可以不匹配，所以将p和右移两位的s继续匹配。
  如果不是：
  判断第一个字符串是不是相同，如果是则将p和s各右移一位进行递归，如果不是返回false了。
  这里有一个额外的知识点就是python and 和 or的执行顺序问题，可以这么理解，如果有括号是括号里的先执行，如果不是则按照顺序执行，and的逻辑是如果左边是False，跳过右边，or的逻辑是如果昨天是True，跳过左边。
• 动态规划求解
  动态规划是运筹学的分支，涉及到运筹学了，动态规划解决的是最优化的问题，核心思想就是把大问题拆解为小问题，可以用动态规划求解问题的最大特点是：最优子结构以及重叠子问题两个特点，最优子结构是保证问题可以拆解的，重叠子问题是为了防止递归重复计算的。
  动态规划是值得学习的一个方法，笔者正在学习中，这里简单说一下自己的理解，如果有不对的地方请大家批评指正。
  动态规划最核心的部分是建立一个矩阵，存储之前计算的结果，防止重复计算。
  放到这个问题，前i个字符串是否匹配是没必要重复计算的，所以需要建立一个矩阵dp来存放。
  定义状态函数f(i,j)，表示字符串p的前i个字符和正则表达式s的前j个字符是否匹配，这里要尤其注意，是前面所有字符，而不是第i个字符和第j个字符。
  然后需要考虑几种不同的情景，第一个要考虑就是空字符串的匹配问题，就是说字符串p是空的时候，什么样的正则可以和他匹配上。我们这么思考，只有或者空才能匹配空字符串。如果定义dp[0,0] = 0那么空字符串都可以匹配上。然后考虑不会单独出现，会和一个字符一起出现，比如a或者ab，所以从正则字符串的第2个开始遍历（j=2:end），如果是则可以不匹配之前的字符串，跟它之前再之前的一个（j-2）状态相同，这个相对比较好理解，因为只涉及一层循环。
  接下来的比较复杂，需要考虑非空字符串的匹配问题。这里还是从最简单的情况入手：
• s[i-1]和p[j-1]相同或者s[i-1]为'.'（可以匹配任意字符）
  这种情况很简单，当前匹配与否和上一个状态完全一致。即：dp[i][j] = dp[i-1][j-1]
• s[i-1]== ''
  这种情况比较复杂，有可能s[i-2]匹配0次，匹配1次，匹配很多次。
  1)匹配0次，直接跳过前一个字符，结果和前前字符相同（注意说的是哪两个字符串相同），即dp[i][j] = dp[i]j-2
  2)匹配1次，前一个字符是匹配得上的，结果和前字符相同，即dp[i][j]=dp[i][j-1]
  3)匹配多次，这个情况比较复杂，如何满足匹配多次的条件呢，需要：p(i-1)和s(j-2)相同，或者s(j-2)是’.’，结果应该和p到上一个字符串位置和s当前字符串匹配结果是相同的，因为到的位置需要匹配多次，所以满足这个规律。

3.python代码

3.1 正则包

import re
class Solution():
    def isMatch(self, p, s):
        return re.match('^'+s+'$', p) is not None

3.2 递归求解

class Solution():
    def isMatch(self, p, s):
        #最简单的情况，s为空
        if not s:
            return not p
        firstmatch = bool(p) and (s[0] == '.' or s[0] == p[0])
        if len(s) > 1 and s[1] == '*':
            return (self.isMatch(p, s[2:]) or
                    firstmatch and self.isMatch(p[1:], s))
        else:
            return firstmatch and self.isMatch(p[1:], s[1:])

3.3 动态规划求解

class Solution():
    def isMatch(self, p, s):
        dp = [[False for _ in range(len(s) + 1)] for _ in range(len(p) + 1)]
        dp[0][0] = True
        for j in range(2, len(s) + 1):
            if s[j-1] == '*':
                dp[0][j] = dp[0][j-2]
        for i in range(1, len(p) + 1):
            for j in range(1, len(s) + 1):
                if s[j - 1] == p[i-1] or s[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]
                if s[j - 1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i][j-2] or dp[i-1][j] and (s[j - 2] == '.' or s[j - 2] == p[i - 1])
        return dp[len(p)][len(s)]