266. 267. Palindrome Permutation

https://leetcode.com/problems/palindrome-permutation/description/

image.png

判断一个单词有没有可能变成回文，其实就是最多允许一个字母出现奇数次，其他的都要偶数次。那么我们就用吊桶来统计词频，最后看看符不符合就好了。

public boolean canPermutePalindrome(String s) {
        int[] map = new int[256];
        for(char c : s.toCharArray()){
            map[c]++;
        }
        int oddCnt = 0;
        for(int i = 0; i < 256; i++){
            if((map[i] & 1) != 0) oddCnt++;
        }
        return oddCnt<=1;
    }

follow up:

image.png

这道题就是一个排列问题，在前一问的基础上，做选择。这题因为要选择摆的位置，我还是使用HASHMAP来存字母频率。先判断有没有，没有直接return空。有的话，就是个排列递归写法。

List<String> res = new ArrayList<>();
    public List<String> generatePalindromes(String s) {
        Map<Character,Integer> map = new HashMap<>();
        for(char c : s.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        int oddCnt = 0;
        char a = 0;
        List<Character> l = new ArrayList<>();
        for(char key : map.keySet()){
            int cnt = map.get(key);
            if((cnt & 1) != 0){
                oddCnt++;
                a = key;
            }
            for(int i =0;i<cnt/2;i++)
                l.add(key);
        }
        if(oddCnt>1) return res;
        help(oddCnt == 1?s.length()-1:s.length(),l,oddCnt == 1?a+"":"",new boolean[l.size()]);
        return res;
    }
    private void help(int rest,List<Character> l,String now,boolean[] seen){
        if(rest == 0){
            res.add(now);
            return ;
        }
        for(int i = 0; i < l.size(); i++){
            if(seen[i]) continue;
            if(i>0 && !seen[i-1] && l.get(i) == l.get(i-1)) continue;
            seen[i] = true;
            help(rest-2,l,l.get(i)+now+l.get(i),seen);
            seen[i] = false;
        }
    }