正则表达式匹配

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

 

说明:

 

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

示例 1:

 

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        if len(p) > 1 and p[1] == "*":
            return self.isMatch(s, p[2:]) or (s and (s[0] == p[0] or p[0] == '.') and self.isMatch(s[1:], p))
        else:
            return s and (s[0] == p[0] or p[0] == '.') and self.isMatch(s[1:], p[1:])


if __name__ == '__main__':
    s = Solution()
    print(s.isMatch("aa", "a"))  # false
    print(s.isMatch("aa", "aa"))  # true
    print(s.isMatch("aaa", "aa"))  # false
    print(s.isMatch("aa", "a*"))  # true
    print(s.isMatch("aa", ".*"))  # true
    print(s.isMatch("ab", ".*"))  # true
    print(s.isMatch("aab", "c*a*b"))  # true