Palindrome Permutation II

(267 Medium)

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

Hint:

If a palindromic permutation exists, we just need to generate the first half of the string.
To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

Java代码

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

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        List<Character> list = new ArrayList<Character>();
        String mid = "";
        for (char c : map.keySet()) {
            if (map.get(c) % 2 != 0) {
                mid += c;
            }
            for (int i = 0; i < map.get(c) / 2; i++) {
                list.add(c);
            }
        }

        if (mid.length() > 1) return result;//more than two elements with odd counts

        boolean[] visited = new boolean[list.size()];
        helper(list, mid, visited, new StringBuilder(), result);
        return result;
    }

    public void helper(List<Character> list, String mid, boolean[] visited, StringBuilder sb, List<String> result) {
        if (sb.length() == list.size()) {
            result.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;//the way we add elements to the list makes sure the same elements are adjacent, no need to sort
            }
            sb.append(list.get(i));
            visited[i] = true;
            helper(list, mid, visited, sb, result);
            visited[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }

利用和All Permutations of String类似的思路

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

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        List<Character> list = new ArrayList<Character>();
        String mid = "";
        for (char c : map.keySet()) {
            if (map.get(c) % 2 != 0) {
                mid += c;
            }
            for (int i = 0; i < map.get(c) / 2; i++) {
                list.add(c);
            }
        }

        if (mid.length() > 1) return result;//more than two elements with odd counts

        StringBuilder builder = new StringBuilder();
       for(int i=0;i<list.size();i++) {
           builder.append(list.get(i));
       }

        permute(builder.toString(),result);

        // Step 4: append the right half of the string
        List<String> result2 = new ArrayList<>();
        for (String str : result) {
            StringBuffer tmp = new StringBuffer(str);
            if (mid != "") {
                tmp.append(mid);
            }

            for (int i = str.length() - 1; i >= 0; i--) {
                tmp.append(str.charAt(i));
            }
            result2.add(tmp.toString());
        }

        return result2;
    }

     void permute( String input,List<String> result) {
        int inputLength = input.length();
        boolean[ ] used = new boolean[ inputLength ];

        StringBuffer outputString = new StringBuffer();
        char[] in = input.toCharArray( );
        Arrays.sort(in);

        doPermute(in, outputString, used,result);
    }

    void doPermute ( char[ ] in, StringBuffer current,
                     boolean[ ] used,List<String> result) {

        if( current.length() == in.length) {
            //System.out.println(current.toString());
            result.add(current.toString());
            return;
        }

        for( int i = 0; i < in.length; ++i ) {
            if( used[i] )
                continue;

            if (i > 0 && in[i] == in[i-1] && used[i-1] == false){
                continue;
            }

            current.append( in[i] );
            used[i] = true;
            doPermute( in,   current, used,result);
            used[i] = false;
            current.deleteCharAt(current.length() - 1);
            //current.setLength(   current.length() - 1 );
        }
    }

References

1. Palindrome Partitioning
2.Palindrome Permutation