Problem

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[].

思路

• 组合出每个string permutation， 然后判断是否是palindrome， 才加进去结果集合中。
• 因为有可能有重复， 所以需要先排序，然后建一个visited的数组
• 时间复杂度： O(n! * n)
• TLE

    public List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<>();
        char[] chs = s.toCharArray();
        Arrays.sort(chs);
        helper(res, new StringBuilder(), chs, new boolean[s.length()]);
        return res;
    }

    private void helper(List<String> res, StringBuilder sb, char[] chs, boolean[] visited) {
        if (sb.length() == chs.length) {
            String s = sb.toString();
            if (isPalindrome(s)) res.add(s);
            return;
        }
        for (int i = 0; i < chs.length; i++) {
            if (visited[i] || i != 0 && chs[i] == chs[i - 1] && !visited[i - 1]) continue;
            visited[i] = true;
            int len = sb.length();
            sb.append(chs[i]);
            helper(res, sb, chs, visited);
            sb.setLength(len);
            visited[i] = false;
        }
    }

    private boolean isPalindrome(String s) {
        int left = 0; 
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }

优化

1. 先判断这个string字符的个数能否组成一个palindrome， 如果存在一个以上的字符个数是奇数，那么不符合
2. 组成一个palindrome permutation实质上将个数是奇数的字符放在中间，然后从其他字符的list中选取元素组成前半段，那么后半段自然就是前半段的反转。 这样就可以直接拼接了。
3. 时间复杂度：O((n/2)! * n/2)
4. 有一点容易错的是： stringbuilder 反转后要反回去，不然bactracking会出错

    public List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<>();
        int[] map = new int[256];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)]++;
        }
        int count = 0;
        for (int num: map) {
            if (num % 2 != 0) count++;
        }
        if (count > 1) return res;

        List<Character> chl = new ArrayList<>();
        String mid = "";
        for (int c = 0; c < map.length; c++) {
            if (map[c] == 0) continue;
            if (map[c] % 2 != 0) mid += (char)c;
            for (int i = 1; i <= map[c] / 2; i++) {
                chl.add((char)c);
            }
        }
        System.out.println(chl);

        helper(res, chl, new boolean[chl.size()], mid, new StringBuilder());
        return res;
    }

    private void helper(List<String> res, List<Character> list, boolean[] visited, String mid, StringBuilder sb) {
        if (sb.length() == list.size()) {
            res.add(sb.toString() + mid + sb.reverse().toString());
            // 这一条会被忽略
            sb.reverse();
            return;
        }

        for (int i = 0; i < list.size(); i++) {
            if (visited[i] || (i != 0 && list.get(i) == list.get(i - 1) && !visited[i - 1])) continue;
            visited[i] = true;
            int len = sb.length();
            sb.append(list.get(i));
            helper(res, list, visited, mid, sb);
            sb.setLength(len);
            visited[i] = false;
        }
    }