LeetCode 10. 正则表达式匹配

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:]))