267. Palindrome Permutation II

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

For example:
Given s = "aabb", return ["abba", "baab"].
Given s = "abc", return [].

总结见：http://www.jianshu.com/p/883fdda93a66

Solution：Backtracking 排列问题

思路： 预处理 + 排列问题47 Permutations II
http://www.jianshu.com/p/d85bc263b282

Time Complexity: O(N!) Space Complexity: O(N)

Solution Code：

class Solution {
    public List<String> generatePalindromes(String s) {
        
        List<String> result = new ArrayList<>();
        List<Character> list = new ArrayList<>();
        
        int odd = 0;
        String mid = "";
        
        Map<Character, Integer> map = new HashMap<>();

        // step 1. build character count map and count odds
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
            odd += map.get(c) % 2 != 0 ? 1 : -1;
        }

        // cannot form any palindromic string
        if (odd > 1) return result;

        // step 2. add half count of each character to list
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char key = entry.getKey();
            int val = entry.getValue();

            if (val % 2 != 0) mid += key;

            for (int i = 0; i < val / 2; i++) list.add(key);
        }

        // step 3. generate all the permutations
        getPerm(list, mid, new boolean[list.size()], new StringBuilder(), result);

        return result;
    }

    // generate all unique permutation from list, sb: cur_res
    void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> result) {
        if (sb.length() == list.size()) {
            // form the palindromic string
            result.add(sb.toString() + mid + sb.reverse().toString());
            sb.reverse();
            return;
        }

        for (int i = 0; i < list.size(); i++) {
            // avoid duplication
            if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;

            if (!used[i]) {
                used[i] = true; sb.append(list.get(i));
                // recursion
                getPerm(list, mid, used, sb, result);
                // backtracking
                used[i] = false; sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}