267. Palindrome Permutation II

解法1：

此题看起来就是用backtracking，但是如果直接用会TLE。
首先观察，如果一个字符串出现奇数次的字符的个数>1，那一定不能组成回文串。
所以奇数个次数的字符最多一个。并且如果有的话最中间的一定是他。
所以偶数回文串可以分成前后两段，奇数回文串可以分成前中后三段。
我们把所有的字符出现的次数/2，加上中段和reverse过的前段就可以得到一个回文串。
那么问题就转变成了求/2过后的子串的所有的permutation。具体的解法如下

lang: java

class Solution {
    public List<String> generatePalindromes(String s) {

        List<String> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }

        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int odd = 0;
        for (char key : map.keySet()) {
            if (map.get(key) % 2 != 0) {
                odd++;
            }
        }

        if (odd > 1) return res;
        String mid = "";

        // Create the to-be-appended string
        StringBuilder sb = new StringBuilder();

        for (char key : map.keySet()) {
            for (int i = 0; i < map.get(key) / 2; i++) {
                sb.append(key);
            }
            if (map.get(key) % 2 != 0) {
                mid = Character.toString(key);
            }
        }

        // Generate permutations for the sb.toStirng()

        List<String> perm = new ArrayList<>();
        boolean[] visited = new boolean[sb.length()];
        String template = sb.toString();
        char[] temparray = template.toCharArray();
        Arrays.sort(temparray);        
        helper(new String(temparray), "", perm, visited);

        for (String temp : perm) {
            res.add(temp + mid + (new StringBuilder(temp)).reverse().toString());
        }

        return res;
    }

    private void helper(String s, String current, List<String> res, boolean[] visited) {
        if (current.length() == s.length()) {
            res.add(current);
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (!visited[i]) {
                if (i != 0 && s.charAt(i) == s.charAt(i - 1) && !visited[i - 1]) continue;
                visited[i] = true;
                helper(s, current + s.charAt(i), res, visited);
                visited[i] = false;
            }
        }
    }
}