267. Palindrome Permutation II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example 1:

Input: "aabb"
Output: ["abba", "baab"]

Example 2:

Input: "abc"
Output: []

Code

class Solution {
    public List<String> generatePalindromes(String s) {
        int[] dd = new int[26];

        for(char c : s.toCharArray()) {
            dd[c - 'a']++;
        }

        int odd = 0;
        char oddC = 'a';

        for(int i = 0; i < 26; i++) {
            if(dd[i] % 2 == 1) {
                odd++;
                oddC = (char)('a' + i);
            }
        }

        if(odd > 1){
            return new ArrayList<>();
        }

        String base = "";
        int ll = s.length();

        if(odd == 1) {
            base = oddC + "";
            dd[oddC - 'a'] -= 1;
            ll -= 1;
        }

        List<String> res = new ArrayList<>();
        helper(res, base, dd, ll);
        return res;
    }

    private void helper(List<String> res, String base, int[] dd, int ll) {
        if(ll == 0){
            res.add(base);
            return;
        }

        for(int i = 0; i < 26; i++) {
            if(dd[i] == 0) continue;

            dd[i] -= 2;
            char c = (char)('a' + i);
            helper(res, c + base + c, dd, ll - 2);
            dd[i] += 2;
        }

    }
}

class Solution:
    def helper(self, res: List[str], base: str, dd: {}, ll: int):
        if ll == 0:
            res.append(base)
            return

        for key in dd:
            if dd[key] == 0:
                continue
            dd[key] -= 2
            self.helper(res, key + base + key, dd, ll - 2)
            dd[key] += 2

    def generatePalindromes(self, s: str) -> List[str]:
        dd = defaultdict(int)

        for c in s:
            dd[c] += 1

        odd = 0
        odd_c = ''
        for key in dd:
            if dd[key] % 2 == 1:
                odd += 1
                odd_c = key

        if odd > 1:
            return []

        base = ""
        ll = len(s)
        if odd == 1:
            base = odd_c
            dd[odd_c] -= 1
            ll -= 1

        res = []
        self.helper(res, base, dd, ll)
        return res