267. Palindrome Permutation II

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

一刷
题解：

1. 我们首先用map构造词频，并计算出出现次数为单数的character数目。
   例如aaaabbc, a[4], b[2], c
   由于出现次数为单数的character数目小于等于1，满足要求。否则直接返回。
2. 将词频除以2，装入list中，此时list = {a, a, b}
3. palindrome为list的一个perm + mid + 逆序的perm
   注意，由于一个character可能出现多次，那么perm的时候排除这种情况：

 if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;

public class Solution {
    public List<String> generatePalindromes(String s) {
    int odd = 0;
    String mid = "";
    List<String> res = new ArrayList<>();
    List<Character> list = new ArrayList<>();
    Map<Character, Integer> map = new HashMap<>();

    // step 1. build character count map and count odds
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
        odd += map.get(c) % 2 != 0 ? 1 : -1;
    }

    // cannot form any palindromic string
    if (odd > 1) return res;

    // step 2. 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);
    }

    // step 3. generate all the permutations
    getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);

    return res;
}

// generate all unique permutation from list
void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res) {
    if (sb.length() == list.size()) {
        // form the palindromic string
        res.add(sb.toString() + mid + sb.reverse().toString());
        sb.reverse();
        return;
    }

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

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

二刷
同上

public class Solution {
    public List<String> generatePalindromes(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int odd = 0;
        String mid = "";
        List<String> res = new ArrayList<>();
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                map.put(ch, map.get(ch)+1);
                odd += map.get(ch)%2==0? -1:1;
            }else{
                map.put(ch, 1);
                odd++;
            }
        }
        if(odd>1) return res;
        
        List<Character> list = new ArrayList<>();
        //iterate the map
        for(Map.Entry<Character, Integer> entry:map.entrySet()){
            char key = entry.getKey();
            int freq = entry.getValue();
            if((freq&1)==1) mid = String.valueOf(key);
            freq/=2;
            while(freq>0){
                list.add(key);
                freq--;
            }
        }
        
        //perm
        StringBuilder sb = new StringBuilder();
        perm(sb, list, res, mid, new boolean [list.size()]);
        return res;
    }
    
    private void perm(StringBuilder sb, List<Character> list, List<String> res, 
                      String mid, boolean[] visited){
        if(sb.length() == list.size()){
            res.add(sb.toString() + mid + sb.reverse());
            sb.reverse();
            return;
        }
        
        for(int i=0; i<list.size(); i++){
            if(visited[i]) continue;
            if(i>0 && list.get(i) == list.get(i-1) && !visited[i-1]) continue;
            sb.append(list.get(i));
            visited[i] = true;
            perm(sb, list, res, mid, visited);
            sb.setLength(sb.length()-1);
            visited[i]=false;
        }
    }
}