# Time limit exceeds--python, is it cause by deepcopy?

• I got 'time limit exceeds', and the last input is '"ltsqjodzeriqdtyewsrpfscozbyrpidadvsmlylqrviuqiynbscgmhulkvdzdicgdwvquigoepiwxjlydogpxdahyfhdnljshgjeprsvgctgnfgqtnfsqizonirdtcvblehcwbzedsmrxtjsipkyxk", which can be executed quickly on my PC.

I have used the same idea to implement the class using C++ and got passed.

I want to know is there any efficiency problem in my python code (I am new to python). Thanks!

``````class Solution:
# @param s, a string
# @return a list of lists of string
def partition(self, s):
mp = {}
palin_m = self.initMat(s)
return self.partition2(s, len(s), mp, palin_m)
def initMat(self, s):
slen = len(s)
m = [[True]*(slen+1) for i in range(slen)]
for i in range(2,slen+1): # i is length of string
for j in range(0,slen-i+1): # j is starting index of the char of the to-be-checked string(check whether it's palin)
m[j][j+i] = (s[j] == s[i+j-1]) and m[j+1][j+i-1]
return m
def partition2(self, s, end, mp, palin_m):
if end in mp:
return mp[end]
if 0 == end:
mp[end] = [[]]
return mp[end]
elif 1 == end:
mp[end] = [[s[0]]]
return mp[end]
res_all = []
for i in range(end-1,-1,-1):
#if self.is_palin(s[i:end]):
if palin_m[i][end]:
res = copy.deepcopy(self.partition2(s, i, mp, palin_m))
for x in res:
x += [s[i:end]]
res_all += res;
mp[end] = res_all
return mp[end]

#def is_palin2(self, palin_m, ):

def is_palin(self,s):
slen = len(s)
if slen <= 1:
return True
return s[0] == s[-1] and self.is_palin(s[1:-1])``````

• ``````class Solution:
# @param s, a string
# @return a list of lists of string
def partition(self, s):
if len(s) == 0: return []
length = len(s)
s = s[::-1]
dptable = []
# DP computing for substring [0, i]
for i in xrange(length):
i_lst = []
if s[0:i+1] == s[i::-1]: i_lst.append([s[0:i+1]])
for j in xrange(1, i+1):
if s[j:i+1] == s[i:j-1:-1]:
for l in dptable[j-1]:
t = l[:]
t.append(s[j:i+1])
i_lst.append(t)
dptable.append(i_lst)
ans = dptable[-1]
ans = [lst[::-1] for lst in ans]
return ans
``````

My python implementation using DP, without any deep copy.

• why do you use reverse? That is meaningless.

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