72ms, python Solution


  • 0
    H

    O(m*n) time, O(n) space:

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

Log in to reply
 

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