Java solution without recursion


  • 0
    S
    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> r = new ArrayList<>();
            List<Character> list = new ArrayList<>();
            Set<Character> set = new HashSet<>();
            //step 1 - get list of duplicate and unique characters
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);
                if(set.contains(c)){
                    list.add(c);
                    set.remove(c);
                }
                else{
                    set.add(c);
                }
            }
            if(s.length() == 0 || set.size() > 1) //not available
                return r;
            //setp2 - generate first half of strings
            Collections.sort(list);
            int n = list.size();
            r.add("");
            for(int i=0; i<list.size(); i++){
                List<String> tmp = new ArrayList<>();
                for(int j=0; j<r.size(); j++){
                    String str = r.get(j);
                    for(int k=0; k<=str.length(); k++){
                        if(k>0 && str.charAt(k-1) == list.get(i))
                            continue;
                        tmp.add(str.substring(0, k) + list.get(i) + str.substring(k,str.length()));
                    }
                }
                r = tmp;
            }
            //stps3 - generate second half of strings
            Character c = set.size() == 1 ? set.iterator().next() : null;
            for(int i=0; i<r.size(); i++){
                r.set(i, "" + r.get(i) + (c == null ? "" : c) + new StringBuilder(r.get(i)).reverse().toString());
            }
            if(r.size() == 0 && c != null)
                r.add("" + c);
            return r;
        }
    }

Log in to reply
 

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