Python code beats 97% with O(n) space and O(mn) time


  • 1
    T

    Adapt rolling window DP, reduce space complexity to O(len(p))

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

Log in to reply
 

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