# 0267. Palindrome Permutation II
###### tags: `Leetcode` `FaceBook` `Backtracking` `Medium`
Link: https://leetcode.com/problems/palindrome-permutation-ii/
## 思路
首先记录每个元素出现的次数，如果出现奇数次的元素个数大于1，说明不可能形成palindrome，直接return 空list
否则用char[]记录所有出现次数为偶数的character 再用单个char（ch）记录出现次数为奇数的character，然后用backtracking排列char[] 里面的元素，假设排出来的字符串叫str，那么最后的答案就加上str+ch+str.reverse()
由于这题也是固定长度的排列，所以和 [0046. Permutation](https://hackmd.io/-8eJWSdqSayMA47GdqKphg)一样用交换
这题需要用set存，跟46不一样，因为46题array里面不会有重复的字符
## Code

public class Solution {
    List < String > set = new ArrayList < > ();
    public List < String > generatePalindromes(String s) {
        int[] map = new int[128];
        char[] st = new char[s.length() / 2];
        if (!canPermutePalindrome(s, map))
            return new ArrayList < > ();
        char ch = 0;
        int k = 0;
        for (int i = 0; i < map.length; i++) {
            if (map[i] % 2 == 1)
                ch = (char) i;
            for (int j = 0; j < map[i] / 2; j++) {
                st[k++] = (char) i;
            }
        }
        permute(st, 0, ch);
        return new ArrayList < String > (set);
    }
    public boolean canPermutePalindrome(String s, int[] map) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)]++;
            if (map[s.charAt(i)] % 2 == 0)
                count--;
            else
                count++;
        }
        return count <= 1;
    }
    public void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
    void permute(char[] s, int l, char ch) {
        if (l == s.length) {
            set.add(new String(s) + (ch == 0 ? "" : ch) + new StringBuffer(new String(s)).reverse());
        } else {
            for (int i = l; i < s.length; i++) {
                if (s[l] != s[i] || l == i) {
                    swap(s, l, i);
                    permute(s, l + 1, ch);
                    swap(s, l, i);
                }
            }
        }
    }
}