7ms Java Accepted solution


  • 0
    V
    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> answer = new ArrayList<String>();
            int[] alphabet = new int[128];
            int odds = 0;
            for(int i = 0; i < s.length(); i++){
                int idx = s.charAt(i);
                alphabet[idx]++;
                odds = alphabet[idx] % 2 == 1 ? odds+1:odds-1;
            }
            if(odds > 1) return answer;
            String singleElement = "";
            List<Character> chars = new ArrayList<Character>();
            for(int i = 0; i < 128; i++){
                if(alphabet[i] % 2 == 1) singleElement = (char)i + "";
                for(int j = 0; j < alphabet[i] / 2; j++){
                    chars.add((char)(i));
                }
            }
            if(chars.size() == 0){
                answer.add(singleElement);
                return answer;
            }
            List<String> list = getAllPermutations(chars);
            for(String ss : list){
                answer.add(ss+singleElement+new StringBuilder(ss).reverse().toString());
            }
            return answer;
        }
        
        private List<String> getAllPermutations(List<Character> chars){
            if(chars.size() == 1) return Arrays.asList(new String[]{chars.get(0)+""});
            List<String> answer = new ArrayList<String>();
            for(int i = 0; i < chars.size(); i++){
                char c = chars.get(i);
                chars.remove(i);
                List<String> list = getAllPermutations(chars);
                for(String ss : list) answer.add(c+ss);
                chars.add(i, c);
                while((i < chars.size()-1) && chars.get(i) == chars.get(i+1)) i++;
            }
            return answer;
        }
    }

Log in to reply
 

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