An easy and concise java solution


  • 0
    Z

    public class Solution {
    public List<String> generatePalindromes(String s) {
    List<String> ans = new ArrayList<>();
    int[] count = new int[128];

        int i, len = s.length();
        int total = 0;
        
        for(i=0;i<len;i++) {
            count[s.charAt(i) - '\0']++;
        }
        
        if(!palindrome(count)) {
            return ans;
        }
        
        mid = '\0';
        
        for(i=0;i<128;i++) {
            if(count[i] % 2 == 0) {
                count[i] /= 2;
            } else {
                mid = (char)i;
                count[i] /= 2;
            }
            
            total += count[i];
        }
        
        build(ans, count, new char[total], 0);
        
        return ans;
    }
    
    public void build(List<String> ans, int[] count, char[] str, int index) {
        if(index == str.length) {
            String s = new String(str);
            String rs = new StringBuilder(s).reverse().toString();
            
            if(odd) {
                ans.add(s + mid + rs);
            } else {
                ans.add(s + rs);
            }
            
            return;
        }
        
        for(int i=0;i<128;i++) {
            if(count[i] == 0)
                continue;
            str[index] = (char)i;
            count[i]--;
            build(ans , count, str, index + 1);
            count[i]++;
        }
    }
    
    private boolean odd = false;
    private char mid;
    
    public boolean palindrome(int[] count) {
        
        for(int i=0;i<128;i++) {
            if(count[i] % 2 == 1) {
                if(odd)
                    return false;
                else
                    odd = true;
            }
        }
        
        return true;
    }
    

    }


Log in to reply
 

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