267 Palindrome Permutation II

267. Palindrome Permutation II

1. Question

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

For example:

Givens = "aabb", return["abba", "baab"].

Givens = "abc", return[].

2. Implementation

(1) Backtracking

class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<>();
        int[] map = new int[256];
        int odd = 0;

        for (char c : s.toCharArray()) {
            ++map[c];
            odd += (map[c] & 1) == 1 ? 1 : -1;
        }

        if (odd > 1) {
            return res;
        }

        String mid = "";
        int len = 0;

        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                if ((map[i] & 1) == 1) {
                    mid = "" + (char)i;
                    --map[i];
                }
                map[i] /= 2;
                len += map[i];
            }
        }

        getPalindromePermutations("", mid, map, len, res);
        return res;
    }

    public void getPalindromePermutations(String curStr, String mid, int[] map, int len, List<String> res) {
        if (curStr.length() == len) {
            String revStr = new StringBuilder(curStr).reverse().toString();
            res.add(curStr + mid + revStr);
            return;
        }

        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                --map[i];
                getPalindromePermutations(curStr + (char)i, mid, map, len, res);
                ++map[i];
            }
        }
    }
}

3. Time & Space Complexity

Backtracking: 时间复杂度O((n/2)!), 空间复杂度O(n), 递归的深度最多为n/2