10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
解题思路
这是一道很经典的动态规划题目(暂时没整理到动态规划，先空在这里，之后复习动态规划专题再补充上)
回溯法也可以很好的解决这个问题，直接上代码看注释就可以很好的明白
class Solution:
def isMatch(self, s: 'str', p: 'str') -> 'bool':
if (len(p) == 0): # 如果字符模式 patten 为空, 只能匹配空
return len(s) == 0
first_match = (len(s) > 0 ) and ((s[0] == p[0]) or (p[0] == '.')) # 判断首位是否匹配
# 有* 的情况下，*不会是p的第一个字符
if (len(p) >= 2 and p[1] == '*'):
#1 * 作为清零使用，即不用*之前的子串，用剩余的子串跟字符串进行匹配
#2* 作为重复前一个字符使用
return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))
else: # 没有*的情况下
return (first_match and self.isMatch(s[1:], p[1:]))
