题目
（困难）给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明：
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
解答
这道题的难度是困难，但是笔者认为非常经典，有必要好好研究研究。
这里模板匹配有三个主要规则，有些概念需要大家理解：
字符的一一对应；
字符“.”可以代替任何一个字符，暂且称之为取代符；
字符“*”可以表示该符号之前的任何字符可以重复任意次，可以是零，为了便于表示，我们暂且把该符号“*”连同其前方的字符一起成为一个重复子，把符号“*”之前的一个字符称作重复基元素，例如重复子“a*”的重复基元素为“a”，因此，每个重复子由两个字符组成，特殊的，重复基元素“.*”的重复子可以代表任意字符重复任意次，我们称之为任意重复子，这种自由度也就增加了题目的复杂性。
方案1：回溯法
笔者这里的回溯法参考了大神博客，但是是用java写的，力扣可以通过，笔者改成了python版本，表示时间超出限制。不过更加建议下面的方案2，动态规划。
class Solution:
"""
采用回溯法
"""
def isMatch(self, s, p): # 主函数
def remove_repeated_patterns(p): # 删除多于的重复子，例如“a*a*a*”简化为“a*”
p_list = []
i = 0
while i < len(p):
cur_char = p[i]
next_char = p[i+1] if i+1 < len(p) else None
if next_char == '*':
star_pattern = cur_char+next_char
i += 2
if p_list and (p_list[-1] == star_pattern or p_list[-1] == '.*'):
continue
else:
p_list.append(star_pattern)
else:
p_list.append(cur_char)
i += 1
return ''.join(p_list)
def is_empty_pattern(p): # 用于判断模板p可否匹配空字符串
if not p:
return True
if len(p) % 2 != 0:
return False
for idx in range(len(p)):
if idx % 2 == 0:
if p[idx] == '*':
return False
else:
if p[idx] != '*':
return False
return True
def match(s, p):
if len(p) == 0:
return len(s) == 0
if len(s) == 0:
return is_empty_pattern(p)
first_match = len(s) > 0 and ((p[0] == s[0]) or (p[0] == '.'))
if len(p) >= 2 and p[1] == '*':
# 看有没有可能, 剩下的pattern匹配上全部的text
return match(s, p[2:]) or (first_match & match(s[1:], p))
else:
return first_match & match(s[1:], p[1:])
p = remove_repeated_patterns(p)
return match(s, p)
方案2：动态规划（建议）
使用动态规划会使匹配流程简洁很多，动态规划的思想在于以空间换时间，而实际上这道题目的空间开销也不大。
【矩阵定义】
首先，我们定义一个矩阵dp，行数为s的长度，列数为p的长度，矩阵中的每一个元素都是布尔量，dp[i][j]表示s[:i+1]和p[:j+1]的匹配结果。
（给基础薄弱的同学补充一下，python中字符串和列表的下标从零开始，索引左闭右开，s[2:5]表示下标为2的元素到下标为4的元素一共3个，下标5所在的元素不取的。因此可以把dp[i][j]理解为从1到i位置为止的s子串（含i位置）与从1到j位为止的p子串（含j位置）的匹配结果。）
【初始情况】
dp建立初始化为None，这里需要注意的是，为了正确表示i=0和j=0的情况，我们增加了第一行和第一列，并且用不会用到的字符“！”和“？”来填充。
当i和j均为0，空字符串和空字符串是匹配的，设置dp[0][0]=0；
当j为零时，也就是模板p为空字符串时，如果i>0，即如果s不是空字符串，则一定不匹配；
当i为零时，即字符串s为空串，这时需要保证p为空或p是n个重复子的组合才能匹配，这里的n为非负整数，例如"a*b*"等。
【状态方程】
如何得到dp[i][j]呢？我们逐行遍历扩大子串s长度，其中对每个子串[:i+1]，我们逐列遍历探究子模板p[:j+1]是否与之匹配，并及时将计算结果储存在dp矩阵中。根据匹配规则，有三种情况要考虑：
如果子模板p[:j+1]中新增的元素p[j]是取代符“.”，或者p[j]与当前子串s[:i+1]中的最后一个元素s[i]相同，则p[:j+1]与s[:i+1]的匹配与否取决于子模板p[:j]与s[:i]的匹配结果，即dp[i][j]=dp[i-1][j-1]；
-
如果子模板p[:j+1]中新增的元素p[j]是“*”，这时子模板p[j+1]的末尾两个字符就构成了重复子，考虑两种情况：
（1）如果子模板p[j+1]的末尾重复子为任意重复子“.*”，或者重复基元素为当前子串s[:i+1]的最后一个字符s[i]，只要满足下列条件中任一一个条件，即可使p[:j+1]与s[i+1]匹配：
①. 先看看不加“*”时能不能匹配，如果模板子串不加“*”都可以和当前子串匹配，那么加“*”后也没问题，相当于重复子的重复次数是1，数学描述：如果当前子串s[:i+1]和去掉“*”的子模板p[:j]匹配，则s[:i+1]与p[:j+1]匹配；
②. 查看一下将当前子模板末尾的整个重复子（“*”以及之前的一个字符）去掉，能不能和当前子串匹配，如果可以成功匹配，则在子模板中增加重复子也没问题，这时相当于重复子的重复次数为0。数学描述：如果当前子串s[:i+1]和去掉重复子的子模板p[:j-1]匹配，则s[:i+1]与p[:j+1]匹配；
③. 最后，我们再看一下保留子模板中的重复子，去掉当前子串中的最后一个字符c，如果这种情况下可以匹配，那么补回字符c后，因为上一层条件要求重复子中的重复元素不是c就是“.”，因此相当于该重复子恰好可以描述子串中的字符c。数学描述：如果子串s[:i]和当前子模板p[:j+1]匹配，则s[:i]末尾增加p[:j+1]末尾重复子的重复基元素s[i]后，s[i+1]，p[j+1]也一定可以匹配。（2）如果子模板p[j+1]的末尾重复子的重复基元素不是当前子串s[:i+1]的最后一个字符s[i]，这时只能考虑让改重复子的重复次数为零了，也就是说，要求去掉重复子后的子模板和当前子串匹配。数学描述：如果当前子串s[i+1]和p[j-1]匹配，则当前子串s[i+1]与p[j-1]增加重复子后的子模板p[j+1]匹配。
（3）其他情况，s[i+1]与p[j+1]无法匹配，即直接设置dp[i][j]=False。
最后取s[:len(s)]和p[:len(p)]的匹配结果即dp矩阵最右下角的数值dp[-1][-1]返回即可。
这里举个栗子，输入s="aab"，p="c*a*."，得到的dp矩阵是这样：
! c c* c*a c*a* c*a*.
? True False True False True False
a False False False True True True
aa False False False False True True
aab False False False False False True
如果对dp表格每一步的变迁过程感兴趣，读者可以安装pandas扩展包，消除代码中的部分注释运行查看。
class Solution:
def isMatch(self, s: str, p: str):
# 打印当前dp表格，方便大家查看。
# def print_dp(s, p, array):
# import pandas as pd
# df = pd.DataFrame(array, list(s), list(p))
# print(df)
s = "?" + s # 添加字符，防止越界
p = "!" + p
dp = [[None for _ in range(len(p))] for _ in range(len(s))] # 构造dp矩阵
dp[0][0] = True # s和p均为空串，则匹配
for i in range(1, len(s)): # p为空，s不为空则无法匹配，设置第一列为False
dp[i][0] = False
# 当s是空串时，怎样才能使p和s匹配？
for j in range(1, len(p)):
if p[j] == "*" and dp[0][j - 2]: # s为空，p若不为空，则必须为“字符+*”的组合才可匹配
dp[0][j] = True
else:
dp[0][j] = False
# print_dp(s, p, dp) # 打印初始情况下的dp表
for i in range(1, len(s)):
for j in range(1, len(p)):
if p[j] == "." or p[j] == s[i]: # 如果p中新增的字符可以匹配s中新增的字符
dp[i][j] = dp[i - 1][j - 1] # 当前匹配与否取决于s和p中添加字符前的情况
elif p[j] == "*": # 如果遇到“*”
if p[j - 1] == s[i] or p[j - 1] == ".":
dp[i][j] = (dp[i][j - 1] or dp[i][j - 2] or dp[i - 1][j])
elif p[j - 1] != s[i]: # 重复字符的次数只能是1，则观察有该模板之前的情况
dp[i][j] = dp[i][j - 2]
else:
dp[i][j] = False
# print('\n当前字符串s: "{}"， 模板p: "{}"'.format(s[1:i+1], p[1:j+1]))
# print_dp(s, p, dp)
return dp[-1][-1]
执行用时 : 80 ms, 在Regular Expression Matching的Python3提交中击败了86.67% 的用户
内存消耗 : 12.9 MB, 在Regular Expression Matching的Python3提交中击败了98.66% 的用户
如有疑问或建议，欢迎评论区留言~
