题目描述

blablabla

样例

blablabla

算法1

(dp) $O(n^2)$

blablabla

时间复杂度分析：blablabla

Python 代码

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        self.f = [[False] * (len(p) + 1)] * (len(s) + 1)
        return self.dp(0,0,s,p)

    def dp(self, x, y, s, p):
        n = len(s)
        m = len(p)
        if self.f[x][y] != False:
            return True
        if y == m:
            self.f[x][y] = x == n
            return self.f[x][y]
        first = (x < n and (s[x] == p[y] or p[y] == '.'))
        if y + 1 < m and p[y + 1] == '*':
            ans = self.dp(x, y + 2, s, p) or first and self.dp(x + 1, y, s, p)
        else:
            ans = first and self.dp(x + 1, y + 1, s, p)
        self.f[x][y] = ans    
        return self.f[x][y]