Python solution with detailed explanation


  • 0
    G

    Solution

    Palindrome Permutation II https://leetcode.com/problems/palindrome-permutation-ii/

    Simple Backtracking

    • Palindrome can have at-most one odd character.
    • We use this fact to test if we can form palindromes or not. We build a frequency map. If we determine we can build palindromes, then we adjust (decrease by 1) the frequency of the single odd frequency character if there is any.
    • We create a so_far array and if there is an odd frequency character, we place it in the middle.
    • Recursion uses s, e to indicate the start and end of so_far. We iterate the counter and pick the character with non-zero frequency. We place the character and increment/decrement s and e.
    from collections import Counter
    class Solution(object):
        def helper(self, s, e, ctr, so_far, result):
            if s >= e:
                result.append("".join(so_far))
            else:
                for k in ctr:
                    if ctr[k] > 0:
                        sp, ep = so_far[s], so_far[e]
                        so_far[s], so_far[e] = k, k
                        ctr[k] -= 2
                        self.helper(s+1, e-1, ctr, so_far, result)
                        ctr[k] += 2
                        so_far[s], so_far[e] = sp, ep
            return
        
        def generatePalindromes(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            # Build a counter map.
            ctr = Counter(s)
            # Test if the string can form a palindrome or not
            if bool(sum(map(lambda x: x&1, ctr.values())) > 1):
                return []
            odd_ch, so_far = None, [None]*len(s)
            # Find the odd valued character
            for k,v in ctr.items():
                if v & 1:
                    odd_ch = k
            # Decrement frequency of odd valued character by 1.
            # Place it in center of so_far array
            if odd_ch:
                ctr[odd_ch], so_far[len(s)//2] = ctr[odd_ch]-1, odd_ch
            result = []
            self.helper(0, len(s)-1, ctr, so_far, result)
            return result
    

    Another Approach


Log in to reply
 

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