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


    public List<String> generatePalindromes(String s) {

        List<String> res = new ArrayList();

        if(s.length() == 0) return res;

        int odd = 0;

        Map<Character, Integer> map = new HashMap();

        for(char c : s.toCharArray()){
            int num = map.getOrDefault(c, 0);
            map.put(c, ++ num);
            odd ++;
            if((num & 1) == 0) odd -= 2;
        }

        if(odd > 1) return res;

        Set <String> set = new HashSet();

        Helper(set, map, "",s.length());

        res.addAll(set);
        return res;
    }

    private void Helper(Set <String> res, Map<Character, Integer> map, String tmp, int len){

        if(tmp.length() > 0 && (len & 1) == 0 && tmp.length() == len >> 1){
            res.add(tmp + new StringBuilder(tmp).reverse().toString());
            return ;
        }
        Iterator it = map.entrySet().iterator();

        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry)it.next();
            char c = (char) pair.getKey();
            int num = (int) pair.getValue();            

            if(num == 1 && tmp.length() * 2 + 1 == len){
                res.add(tmp + String.valueOf(c) + new StringBuilder(tmp).reverse().toString());
                return;
            }

            int curr_num = num;
            while(curr_num >= 2){
                curr_num -= 2;
                map.put(c, curr_num);
                Helper(res, map, tmp + String.valueOf(c), len);
            }
            map.put(c, num);
        }

    }

results matching ""

    No results matching ""