Python DP(Memorization), 62ms, beats 96%.


  • 0
    2

    Turns out it's not that easy to understand.

    To be honest, I wouldn't recommend people to write it this way.

    And you could do it faster with changing passing str to passing list.

    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            def dp(i, j, s, p, memo):
                if (i, j) in memo:
                    return memo[(i, j)]
                
                if i == -1 or j == -1:
                    memo[(i, j)] = False
                    return memo[(i, j)]
                
                if s[i] == p[j] or p[j] == '.':
                    memo[(i, j)] = dp(i-1, j-1, s, p, memo)
                elif p[j] == '*':
                    if s[i] == p[j-1] or p[j-1] == '.':
                        memo[(i, j)] = dp(i-1, j, s, p, memo) or dp(i-1, j-2, s, p, memo) or dp(i, j-2, s, p, memo)
                    else:
                        memo[(i, j)] = dp(i, j-2, s, p, memo)
                else:
                    memo[(i, j)] = False
                return memo[(i, j)]
            
            memo = {}
            memo[(-1, -1)] = True
            index = 1
            while index < len(p) and p[index] == '*':
                memo[(-1, index)] = True
                index += 2
            return dp(len(s)-1, len(p)-1, s, p, memo)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.