Python O(m*n) space and O(2*n) space


  • 0
    S
    class Solution(object):
    # O(m*n) space
    def isMatch1(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m,n = len(s), len(p)
        dp = [[True]+[False]*m for _ in range (n+1)]
        for i in range (1, n+1):
            if p[i-1] == "*":
                if i ==1: dp[i][0] = True
                else: dp[i][0] = dp[i-2][0] or False
            else:
                dp[i][0] = False
            for j in range (1, m+1):
                if p[i-1] != "*":
                    dp[i][j] = dp[i-1][j-1] and (p[i-1] == s[j-1] or p[i-1] == ".")
                else:
                    if i == 1: dp[i][j] = False
                    else: dp[i][j] = dp[i-2][j] or dp[i-1][j] or (dp[i][j-1] and (s[j-1] == p[i-2] or p[i-2] == "."))
        return dp[-1][-1]
    
    # O(2*n) space
    def isMatch(self, s, p):
        m, n = len(s), len(p)
        dp = [[]]
        dp.append([True]+[False]*m)
        for i in range (1, (n+1)):
            cur = []
            if p[i-1] == "*":
                if i==1:cur.append(True)
                else:cur.append(dp[0][0])
            else:
                cur.append(False)
            for j in range (1, m+1):
                if p[i-1] != "*":
                    cur.append(dp[1][j-1] and (p[i-1] == s[j-1] or p[i-1] == "."))
                else:
                    if i==1:
                        cur.append(False)
                    else:
                        cur.append(dp[0][j] or dp[1][j] or (cur[j-1] and (s[j-1] == p[i-2] or p[i-2] == ".")))
            dp.pop(0)
            dp.append(cur)
        return dp[-1][-1]

Log in to reply
 

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