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

• 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

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