How can I improve this Python solution to avoid TLE?


  • 0
    0
    class Solution(object):
    def generatePalindromes(self, s):
    
        permutations = []
        result = []
        self.dfs(sorted(s),[],permutations)
        for permed in permutations:
            if permed ==  str(self.reverse(list(permed),0,len(list(permed))-1)):
                result.append(permed)
            
        
        return result
        
        ## Here I'm basically going through each letter and generate all it's palindromes: Using Permutation II way.
    def dfs(self,string,subperm,perms):
        if len(string) == 0:
            perms.append(''.join(subperm))
        for i in xrange(len(string)):
            if i >0 and string[i] == string[i-1]:
                continue
            self.dfs(string[:i] + string[i+1:],subperm + [string[i]],perms)
            
    ## This is a helper method to check for the palindrome out of the Permutations, since not all of the permutations are palindromes.
    def reverse(self,string,start,end):
        while start < end:
            string[start],string[end] = string[end],string[start]
            start +=1
            end -= 1
        return ''.join(string)
    

    little improved, but still getting TLE:

    class Solution(object):
    def generatePalindromes(self, s):
    
        permutations = []
        self.dfs(sorted(s),[],permutations)
        return permutations
        
        
    def dfs(self,string,subperm,perms):
        if len(string) == 0:
            permed = ''.join(subperm)
            if permed == self.reverse(list(permed),0,len(permed)-1):
                perms.append(''.join(subperm))
        for i in xrange(len(string)):
            if i >0 and string[i] == string[i-1]:
                continue
            self.dfs(string[:i] + string[i+1:],subperm + [string[i]],perms)
            
    def reverse(self,string,start,end):
        while start < end:
            string[start],string[end] = string[end],string[start]
            start +=1
            end -= 1
        return ''.join(string)

Log in to reply
 

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