Normal DP


  • 1
    class Solution(object):
        def isMatch(self, s, p):
            dp = [ [ False for i in xrange(len(p) + 1) ] for j in xrange(len(s) + 1) ]
            dp[0][0] = True
            for i in xrange(len(p)):
                dp[0][i + 1] = False if p[i] != '*' else dp[0][i - 1]
            for i in xrange(1, len(s) + 1):
                for j in xrange(1, len(p) + 1):
                    dp[i][j] = dp[i - 1][j - 1] if(p[j - 1] == s[i - 1] or p[j - 1] == '.') else ( (dp[i][j - 2] or dp[i][j - 1] or (dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == '.') )) if p[j - 1] == '*' else False)
            return dp[-1][-1]
    

Log in to reply
 

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