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


  • 0
    C

    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])

  • 0
    K
    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.


  • 0
    H

    why do you use reverse? That is meaningless.


Log in to reply
 

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