My straight forward Java Solution


  • 1
    T
    public class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> res= new ArrayList<>();
        String newS = new String();
        if(s == null || s.length() == 0) {
            return res;
        }
        Map<Character, Integer> map =  new HashMap<>();
        int oddCount = 0;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(map.get(c) == null) {
                map.put(c, 1);
            }
            else {
                map.put(c, map.get(c) + 1);
            }
        }
        int[][] mapAry = new int[2][map.size()];
        int col = 0;
        for(Map.Entry<Character, Integer> entry : map.entrySet()) {
            mapAry[0][col] = entry.getKey();
            mapAry[1][col] = entry.getValue();
            col++;
        }
        int countOdd = 0;
        int oddIndex = 0;
        for(int i = 0; i < mapAry[1].length; i++) {
            if(countOdd == 0 && mapAry[1][i] % 2 == 1) {
                countOdd++;
                oddIndex = i;
            }
            else if(mapAry[1][i] % 2 == 1){
                 return res;
            }
        }
        if(countOdd > 0) {
            newS = "" + (char)mapAry[0][oddIndex];
            mapAry[1][oddIndex]--;
        }
        helper(mapAry, s, res, newS);
        return res;
    }
    
    public void helper(int[][] mapAry, String s, List<String> res, String newS) {
        if(newS.length() == s.length()) {
            res.add(new String(newS));
        }
        for(int i = 0; i < mapAry[0].length; i++) {
            if(mapAry[1][i] > 0) {
                mapAry[1][i] -= 2;
                newS = (char)mapAry[0][i] + newS + (char)mapAry[0][i];
                helper(mapAry, s, res, newS);
                newS = newS.substring(1, newS.length() - 1);
                mapAry[1][i] += 2;
            }
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.