class Solution:
    def match(self , str: str, pattern: str) -> bool:
        if not pattern:
            return not str

        firstMatch = str and pattern[0] in {str[0], '.'}
        if len(pattern) >= 2 and pattern[1] == '*':
            return (self.match(str, pattern[2:]) or firstMatch and self.match(str[1:], pattern))
        else:
            return firstMatch and self.match(str[1:], pattern[1:])

解题思路

本题采用的是递归的思想。

• 如果pattern不存在的话，就返回not str（当str不存在时，二者可以匹配上，返回True；都则返回False）。
• 给firstMatch赋值，如果str还有，并且pattern[0]==str[0]或者是等于'.'，则为True；否则为False。
• 如果当前pattern长度大于等于2，并且pattern[1]等于'*'，则返回（pattern[2:]后的匹配结果）或（firstMatch and str[1:]后的匹配结果）；否则的话，返回firstMatch and （str[1:]，pattern[1:]后的匹配结果）。

复杂度

• 时间复杂度和空间复杂度都为O（mn）。