Pretty easy, but long code...


  • 0
    public class Solution {
        public List<String> generatePalindromes(String s) {
            if (s.length() == 0) return new ArrayList();
            int[] map = new int[128];
            for (char c:s.toCharArray()) {
                map[c]++;
            }
            int countOne = 0;
            char mid = 0;
            String myS = "";
            for (int i = 0; i < 128; i++) {
                if (map[i] == 0) continue;
                if ((map[i]&1) != 0) {
                    mid = (char)i;
                    countOne++;
                    for (int j = 0; j < map[i]/2; j++) {
                        myS += (char)i;
                    }
                } else {
                    for (int j = 0; j < map[i]/2; j++) {
                        myS += (char)i;
                    }
                }
                if (countOne > 1) return new ArrayList();
            }
            List<String> res = new ArrayList<>();
            if (s.length() == 1) {
                res.add(mid + "");
                return res;
            }
            boolean[] vis = new boolean[myS.length()];
            dfs(myS, res, new StringBuilder(), vis);
            // add another part
            for (int i = 0; i < res.size(); i++) {
                String cur = res.get(i);
                cur = cur + ((countOne == 1) ? mid : "") + (new StringBuilder(cur).reverse().toString());
                res.set(i, cur);
            }
            return res;
        }
        
        private void dfs(String myS, List<String> res, StringBuilder sb, boolean[] vis) {
            if (sb.length() == myS.length()) {
                res.add(sb.toString());
                return;
            }
            for (int i = 0; i < myS.length(); i++) {
                if (vis[i] || (i > 0 && !vis[i-1] && myS.charAt(i) == myS.charAt(i-1))) continue;
                vis[i] = true;
                int len = sb.length();
                dfs(myS, res, sb.append(myS.charAt(i)), vis);
                sb.setLength(len);
                vis[i] = false;
            }
        }
    }
    

Log in to reply
 

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