Leetcode #267. Palindrome Permutation II

[yokostan]

HashMap to count the characters and then backtracking to construct the String in a separate function with boolean[] visited and list.get(i) == list.get(i - 1) trick! Solution:

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

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int countOdd = 0;
        for (Character c : map.keySet()) {
            if (map.get(c) % 2 == 1) {
                countOdd++;
            }
        }

        if (countOdd > 1) return res;

        List<Character> list = new ArrayList<>();
        String mid = "";

        //add half count of each character to list
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char key = entry.getKey();
            int val = entry.getValue();
            if (val % 2 != 0) mid += key;
            for (int i = 0; i < val / 2; i++) list.add(key);
        }

        boolean[] visited = new boolean[list.size()];

        getPerm(list, mid, visited, new StringBuilder(), res);

        return res;
    }

    private void getPerm(List<Character> list, String mid, boolean[] visited, StringBuilder sb, List<String> res) {
        if (sb.length() == list.size()) {
            res.add(sb.toString() + mid + sb.reverse().toString());
            sb.reverse();
            return ;
        }

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

            if (!visited[i]) {
                visited[i] = true;
                sb.append(list.get(i));
                getPerm(list, mid, visited, sb, res);
                visited[i] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}