leetcode——10.正则表达式匹配

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: 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=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 and dp(i+1,j))
            else:
                ans=first and dp(i+1,j+1)
            memo[(i,j)]=ans
            return ans
        return dp(0,0)

执行用时 :48 ms, 在所有 python3 提交中击败了98.77%的用户

内存消耗 :14 MB, 在所有 python3 提交中击败了5.04%的用户

 

这道题在我现在看来还是很难的，答案也是看来好几遍才懂。

幸亏看了公众号labuladong的关于这道题的算法分析，才让我豁然开朗，真的好牛逼哦。

 

加油啊，在动态规划的道路上扎根。

 

                                                                       ——2019.10.17