267.Palindrome Permutation II

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

Analysis

用DFS 的 swap过来在swap过去的方法

Better Solution

We only need to generate the first part of palindrome string, and the remaining part will be a middle character with the reverse of first part.

helper function dfs不需要用Set来去除duplicates, 因为array中同一个字母在其所在位置只能出现一次

 public List<String> generatePalindromes(String s) {
        int[] hash = new int[256];
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        char[] input = s.toCharArray();
        int odd = 0;
        int len = 0;
        for (char c : input) {
            hash[c]++;
        }
        for (int i=0; i<256; i++) {
            if (hash[i] % 2 == 1) {
                odd++;
                if (odd > 1) {
                    return result;
                }
                sb.append((char)i);
                hash[i]--;
            }
            hash[i] /= 2;
            len += hash[i];
        }
        String mid = sb.toString();
        sb.setLength(0);
        helper(hash, len, sb, mid, result);
        return result;
    }
    private void helper(int[] hash, int len, StringBuilder sb, String mid, List<String> result) {
        if (sb.length() == len) {
            result.add(sb.toString() + mid + sb.reverse().toString());
            sb.reverse();
            return;
        }
        for (int i=0; i<hash.length; ++i) {
            if (hash[i] > 0) {
                sb.append((char)i);
                hash[i]--;
                helper(hash, len, sb, mid, result);
                sb.deleteCharAt(sb.length()-1);
                hash[i]++;
            }
        }
    }

My Solution

这个解法超时了. 思路是先把array sort一下, 然后用swap过来在swap过去的方法(因为只是相对顺序变了), DFS暴力找。Time Complexity太高(n! n * n-1 * n-2 *........).

Better Solution是只用DFS一半的array, 因为后半段是一样的........

public List<String> generatePalindromes(String s) {
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        HashSet<String> set = new HashSet<>();
        char[] input = s.toCharArray();
        Arrays.sort(input);
        helper(input, 0, sb, set, result);
        return result;
    }
    private void helper(char[] input, int index, StringBuilder sb, HashSet<String> set, List<String> result) {
        if (index == input.length) {
            String temp = sb.toString();
            if (temp.length() > 0 && isPal(temp) && set.add(temp)) {
                result.add(temp);
            }
            return;
        }
        for (int i=index; i<input.length; ++i) {
            sb.append(input[i]);
            swap(input, index, i);
            helper(input, index+1, sb, set, result);
            swap(input, index, i);
            sb.deleteCharAt(sb.length()-1);
        }
    }
    private void swap(char[] input, int left, int right) {
        char temp = input[left];
        input[left] = input[right];
        input[right] = temp;
    }
    private boolean isPal(String s) {
        char[] input = s.toCharArray();
        int i = 0; int j = input.length - 1;
        while (i < j) {
            if (input[i] != input[j]) {
                return false;
            }
            i++; j--;
        }
        return true;
    }

Hint:

If a palindromic permutation exists, we just need to generate the first half of the string.