题目描述

blablabla

样例

blablabla

算法1

(dp) $O(nm)$

python 代码

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        n = len(s)
        m = len(p)
        f = [[False] * (m+1) for i in range(n+1)]
        s = ' ' + s
        p = ' ' + p
        f[0][0] = True

        for i in range(n+1):
            for j in range(1, m+1):
                if j + 1 < m and p[j+1] == '*':
                    continue
                if i and p[j] != '*':
                    if s[i] == p[j] or p[j] == '.':
                        f[i][j] = f[i-1][j-1]
                elif p[j] == '*':
                    f[i][j] = f[i][j-2] or (f[i-1][j] and (s[i] == p[j-1] or p[j-1] == '.'))
        return f[n][m]