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

1
2
3
4
5
Input: "aabb"
Output: ["abba", "baab"]

Input: "abc"
Output: []

附: permutations，如果本身nums数组就都是distinct integers, 就不需要used数组；如果包含duplicates而此时要全排列，就都是需要used[]数组记录是不是使用过的

  1. 数每个character，看能不能成palindrome
  2. 拼一半character，记录mid, 得到拼palindrome的原材料
  3. dfs + backtracking 得到所有的palindrome
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public List<String> generatePalindromes(String s) {
        int odd = 0;
        String mid = "";
        List<String> res = new ArrayList<>();
        List<Character> list = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        
        // 1. count #characters, 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);
            // 因为c对应的value由1变成了2, 3变成了4这种，所以偶数的时候是-1,不是0
            odd += map.get(c) % 2 != 0 ? 1 : -1;
        }
        
        // cannot form any palindrome string; 
        if (odd > 1) return res;
        
        // 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);
        }
        
        // 3. generate all permutations
        getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);
        
        return res;
    }
    
    void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res) {
        if (sb.length() == list.size()) {
            res.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));
                getPerm(list, mid, used, sb, res);
                used[i] = false; sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}