Python recursive solution


  • 0
    A

    Use a recursive function to create palindrome

    def generatePalindromes(self, s):
        self.m = {}
        for c in s:
            if c not in self.m:
                self.m[c] = 0
            self.m[c] += 1
            
        oddCount = 0
        middle = ''
        for k in self.m.keys():
            if self.m[k] % 2:
                middle = k
                self.m[k] -= 1
                oddCount += 1
        
        if oddCount > 1:
            return []
        
        self.ans = []
        self.createPalin(middle)
        return self.ans
    
    def createPalin(self, s):
        noMore = True
        for k in self.m.keys():
            if self.m[k] == 0:
                continue
            self.m[k] -= 2
            self.createPalin(k + s + k)
            self.m[k] += 2
            noMore = False
        
        if noMore:
            self.ans.append(s)

Log in to reply
 

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