6ms easy-to-understand Java Solution


  • 0
    public class Solution {
        
        public List<String> getPermutation(String s) {
            List<String> lst = new ArrayList<String>();
            for(int i=0; i<s.length(); i++) {
                List<String> subLst = getPermutation(new StringBuilder(s).deleteCharAt(i).toString());
                if(subLst.isEmpty())
                    lst.add(""+s.charAt(i));
                else {
                    for(String str : subLst)
                        lst.add(""+s.charAt(i)+str);
                }
                while(i<s.length()-1 && s.charAt(i+1)==s.charAt(i)) // skip duplicates
                    i++;
            }
            return lst;
        }
        
        public List<String> generatePalindromes(String s) {
            int[] map = new int[256];
            for(int i=0; i<s.length(); i++)
                map[s.charAt(i)]++;
            boolean foundOdd = false;
            char oddChar = 0;
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<map.length; i++) {
                if(map[i]%2==1) {
                    if(foundOdd)
                        return new ArrayList<String>(); // s cannot be palindrome
                    foundOdd = true;
                    oddChar = (char)i;
                }
                for(int j=0; j<map[i]/2; j++)
                    sb.append((char)i);
            }
            List<String> lst = getPermutation(sb.toString());
            List<String> fullLst = new ArrayList<String>();
            if(lst.isEmpty() && foundOdd)
                fullLst.add(""+oddChar);
            else if(foundOdd) {
                for(String str : lst)
                    fullLst.add(str+oddChar+(new StringBuilder(str).reverse().toString()));
            } else {
                for(String str : lst)
                    fullLst.add(str+(new StringBuilder(str).reverse().toString()));
            }
            return fullLst;
        }
    }

Log in to reply
 

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