Simple recursive method using python


  • 0
    S
    class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if(len(s)==0):
            return []
        dic = {}
        res=[]
        for i in range (0, len(s)):
            if s[i] in dic:
                dic[s[i]] +=1
            else:
                dic[s[i]] = 1
        temp = [None]*len(s)
        if(len(s)%2==0):
            if (self.even(dic)):
                self.helper(0, len(s)-1, temp, res, dic)
        else:
            if(self.odd(dic)):
                self.helper(0, len(s)-1, temp, res, dic)
        return list(set(res))
           
    def even(self, dic):
        for each in dic:
            if( dic[each]%2 !=0):
                return False
        return True
    
    def odd(self, dic):
        flag = False
        for each in dic:
            if(dic[each]%2!=0 and flag):
                return False
            elif(dic[each]%2!=0 and not flag):
                flag = True
        return True
    
    def helper(self, start, end, temp, res, dic):
        for key in dic.keys():
            if(start > end):
                res.append("".join(temp))
                return
            if(start == end):
                if(dic[key] ==1):
                    temp[start]=key
                    res.append("".join(temp))
                    return
                else:
                    continue
            if(dic[key]>=2):
                temp[start] = key
                temp[end] = key
                dic[key]-=2
                self.helper(start+1, end-1, temp, res, dic)
                dic[key]+=2

Log in to reply
 

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