Simple Python DFS solution


  • 0
    G
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if not s:
            return []
        s_count = collections.Counter(s)
        
        odd_char = None
        half_s = ''
        
        for c, freq in s_count.items():
            if freq%2 == 1:
                if odd_char:
                    return []
                odd_char = c
            half_s += c * (freq//2)
        
        half_perm = []
        self.dfs(half_s, '', half_perm)
        res = []
        
        if odd_char is None:
            for half in half_perm:
                res.append(half + half[::-1])
        else:
            for half in half_perm:
                res.append(half + odd_char + half[::-1])
        return res
            
            
        
        
    def dfs(self, s, path ,res):
        if not s:
            res.append(path)
        for i in range(len(s)):
            if i > 0 and s[i] == s[i-1]:
                continue
            self.dfs(s[:i] + s[i+1:], path + s[i], res)

Log in to reply
 

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