Accepted java solution.


  • 0
    M
    public class Solution {
        public List<String> generatePalindromes(String s) {
    
    
            if (s == null || s.length() == 0)
                 return new ArrayList<String>();
    
            // Odd string length would mean one character that stays in center for all palindromes.
            boolean odd = s.length() % 2 == 1;
            
            // Count each character, how many times it occurs in string.
            HashMap<Character, Integer> chars = new HashMap<Character, Integer>();
            int size = 0;
            for (char ch : s.toCharArray()) {
                
                Integer count = chars.get(ch);
                if (count == null) {
                    chars.put (ch, 1);
                } else {
                    int val = count.intValue();
                    chars.put (ch, ++val);
                }
            }
    
            // create new character array with unique characters for left half of palindrome to generate all permutations. A unique character appears once if it appears 2 times in the original string. A unique character may appear more than once if the count of that character is more than 2. If a unique character has odd count like 1 or 3 then it will appear in center and if odd count is > 1 then that character is additionally added correspondingly to the new character array. Also center occurance is remembered in the variable oddOne.
    
            for (int i : chars.values()) {
                if (i % 2 == 1) {
                    size+= i/2;
                    if (odd)
                        odd = false;
                    else // More than one character has odd count or string is even length and so no palindrome possible
                        return new ArrayList<String>();
                } else {
                    size += i / 2;
                }
            }
            char[] newArray = new char[size];
            int index = 0;
            char oddOne = 0;
            for (Map.Entry<Character,Integer> m : chars.entrySet()) {
                Integer val = m.getValue();
                Character c = m.getKey();
                if (val.intValue() %2 == 1) {
                    oddOne = c;
                  for (int k = 0; k < val.intValue()/2; k++) {
                        newArray[index++] = c;
                    }  
                } else {
                    for (int k = 0; k < val.intValue()/2; k++) {
                        newArray[index++] = c;
                    }
                }
            }
            return generatePermutations(newArray, 0, oddOne);
        }
        
        List<String> generatePermutations (char[] array, int i, char oddOne) {
            
            // > is needed in case array length is 0 which is the case when there is only one character in string.
            if (i >= (array.length - 1) ){
                StringBuffer str = new StringBuffer();
                for (int j = 0 ; j < array.length; j++) {
                    str.append(array[j]);
                }
    
                // center of palindrome when original string length is odd
                if (oddOne != 0) {
                    str.append(oddOne);
                }
                // generate the rest of the palindrome by taking left side and reversing it and adding to the array.
                for (int j = array.length - 1; j >= 0; j--) {
                    str.append(array[j]);
                }
                ArrayList<String> list =  new ArrayList<String>();
                list.add(str.toString());
                return list;
            } else {
                ArrayList<String> list = new ArrayList<String>();
                for (int j = i; j < array.length; j++) {
                    // don't regenerate permutations swapping with same character in a different position to avoid duplicates.
                    if (array[j] == array[i] && i != j)
                        continue;
                    swap (i, j, array);
                    list.addAll (generatePermutations(array, i+1, oddOne));
                    swap (i, j, array);
                }
                return list;
            }
            
        }
        void swap (int i, int j, char[] array) {
            char temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

Log in to reply
 

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