Description

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

Example

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

Givens = "abc", return[].

Solution

按照Palindrome Permutation I的思路求出前半边result string的characters
再按照Permutation的思路求出这些characters组成的没有重复的permutations
最后补成对称的string

class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }

        Set<Character> set = new HashSet<Character>();
        List<Character> chars = new ArrayList<Character>();
        for (char c : s.toCharArray()) {
            if (!set.contains(c)) {
                set.add(c);
            } else {
                chars.add(c);
                set.remove(c);
            }
        }

        if (s.length() % 2 != set.size()) {
            return result;
        }

        Collections.sort(chars);
        boolean[] visited = new boolean[chars.size()];
        StringBuffer sb = new StringBuffer();
        palindrome(chars, result, sb, visited, set);
        return result;
    }

    private void palindrome(List<Character> chars, List<String> result, StringBuffer sb, boolean[] visited, Set<Character> set) {
        if (sb.length() == chars.size()) {
            result.add(buildPalindrome(new StringBuffer(sb), set));
            return;
        }

        for (int i = 0; i < chars.size(); i++) {
            if (!visited[i]) {
                if (i > 0 && chars.get(i) == chars.get(i - 1) && !visited[i - 1]) {
                    continue;
                }

                visited[i] = true;
                sb.append(chars.get(i));
                palindrome(chars, result, sb, visited, set);
                visited[i] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    private String buildPalindrome(StringBuffer sb, Set<Character> set) {
        for (char c : set) {
            sb.append(c);
        }

        for (int i = set.size() == 0 ? sb.length() - 1 : sb.length() - 2; i >= 0; i--) {
            sb.append(sb.charAt(i));
        }

        return sb.toString();
    }
}