Python solution sharing: Preprocess, then it would be like ordinary backtracking permutation!


  • 3
    O

    Take aabbbcc as an example

    counter would be {"a":2, "b":3, "c":2}

    After preprocess: baseStr = "abc", mid = "b" (if there is no char happens odd times, mid = "")

    Then use backtracking to find all the permutation of baseStr,

    the valid palindrome would be "permuStr + mid + reverseOfPermuStr"

    def generatePalindromes(self, s):
        counter = collections.Counter(s)
        odds = filter(lambda x: x % 2, counter.values())
        if len(odds) > 1:
            return []
        baseStr, mid = self.preProcess(counter)
        return self.backTracking(baseStr, 0, mid, [baseStr + mid + baseStr[::-1]])
        
    def preProcess(self, counter):
        baseStr = mid = ""
        for char in counter:    
            if counter[char] % 2:
                mid = char
            baseStr += char*(counter[char]/2)
        return baseStr, mid
        
    def backTracking(self, s, idx, mid, ans):
        if idx == len(s) - 1:
            return ans
        for i in range(idx, len(s)):
            if i >= 1 and s[i] == s[i-1] == s[idx]:
                continue #no need to go deeper if swap would be the same
            #Swap s[idx] with s[i]
            if i != idx:
                permu = s[:idx] + s[i] + s[idx+1:i] + s[idx] + s[i+1:] 
                ans.append(permu + mid + permu[::-1])
            else:
                permu = s
            self.backTracking(permu, idx+1, mid, ans)
        return ans

  • 1
    C

    not work for case "aaaabbbb"


  • 2
    X

    As your solution is not working in some cases, e.g. 'aaaabbbbcccc'. I modified it as following and it passed now. Thank you for sharing your idea.

    class Solution(object):
        def generatePalindromes(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            # Get dictionary map char to its appearance
            counter = collections.Counter(s)
            mid, base, res = '', '', []
            # Get mid char and base string
            for c in counter:
                if counter[c] % 2 != 0: 
                    if mid: return []
                    else: mid = c
                base += c * (counter[c] // 2)
            # Start backtracking
            self.backTracking(base, 0, mid, res)
            return res
        
        def backTracking(self, base, start, mid, res):
            # No char to be permuted, which means reach out the leaf in the tree
            if start == len(base):
                res.append(base + mid + base[::-1])
                return
            # Loop to permute char @ start with itself and all following different char 
            for i in range(start, len(base)):
                # Prune the branch as duplicated!!!
                if i > start and (base[i] == base[i-1] or base[i] == base[start]):
                    continue
                # Get the permutation
                perm = base if i == start else base[:start] + base[i] + base[start+1:i] + base[start] + base[i+1:]
                # Permute next char with following chars
                self.backTracking(perm, start+1, mid, res)
    

  • 0
    D
    This post is deleted!

Log in to reply
 

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