2015年9月10日星期四

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 class Solution {
    public List<String> generatePalindromes(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        Character odd = null;
        for (Character c : map.keySet()) {
            int num = map.get(c);
            if (num % 2 == 1) {
                if (odd != null) return new ArrayList<String>();
                else {
                    odd = c;
                    map.put(c, num - 1);
                }
            }
        }
        String cur = odd == null ? "" : Character.toString(odd);
        List<String> strs = new ArrayList<String>();
       
        helper(map, cur, strs, s.length());
        return strs;
    }
   
    private void helper(HashMap<Character, Integer> map, String cur, List<String> res, int len) {
        if (cur.length() == len) {
            res.add(cur);
        } else {
            for (Character c : map.keySet()) {
                if (map.get(c) == 0) {
                    continue;
                }
                int val = map.get(c);
                map.put(c, val - 2);
                helper(map, c + cur + c, res, len);
                map.put(c, val);
            }
        }
    }
}

没有评论:

发表评论