Clean python DP code, beats 91% and clean backtracking code that beats 85%


  • 0
    Y

    The code can be further optimized to reduce space by recording start index and end index of substring instead of recording the entire substring

    def check(s, l, r):
        if l == r:
            return True
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                return False
        return True
    class Solution(object):
        def partition(self, s):
            """
            :type s: str
            :rtype: List[List[str]]
            """
            if len(s) == 0: return [[]]
            dp = [[[] for x in range(len(s))] for y in range(len(s))]
            for i in range(len(s)):
                if check(s, 0, i):
                    dp[0][i].append([s[:i+1]])
                for j in range(i):
                    if len(dp[0][j]) == 0:
                        continue
                    if check(s, j+1, i):
                        string = s[j+1:i+1]
                        for strList in dp[0][j]:
                            newList = list(strList)
                            newList.append(string)
                            dp[0][i].append(newList)
            return dp[0][len(s)-1]
    
    def check(s, l, r):
        if l == r:
            return True
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                return False
        return True
    
    class Solution(object):
        def partition(self, s):
            """
            :type s: str
            :rtype: List[List[str]]
            """
            if len(s) == 0:
                return []
            res = []
            for i in range(len(s)):
                if check(s, 0, i):
                    if i == len(s) - 1:
                        res.append([s[:i+1]])
                    li = self.partition(s[i+1:])
                    for l in li:
                        res.append([s[:i+1]] + l)
            return res
    

Log in to reply
 

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