leetcode-10-线性DP-正则表达式匹配

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 递归 + 备忘录
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = dict()
        def dp(i, j):
            if (i, j) in memo : return memo[(i, j)]
            if(j == len(p)): return i == len(s)

            first_match = (i < len(s)) and p[j] in {s[i], '.'}
            if((j <= len(p)-2) and (p[j+1] == '*')):
                ans = dp(i, j+2) or (first_match and dp(i+1, j))
            else:
                ans = first_match and dp(i+1, j+1)

            memo[(i,j)] = ans
            return ans

        return dp(0, 0)

参考

正则表达式匹配