Clean java solution using dfs to generate the palindrome permutation


  • 0
    S
    public class Solution {
    public List<String> generatePalindromes(String s) {
        int[] map = new int[256];
        for(char ch : s.toCharArray())
            map[ch]++;
        boolean single = false;
        String singleChar = "";
        int len = s.length(), p = 0;
        char[] half = new char[len/2];
        List<String> res = new ArrayList<>();
        for(int i = 0; i < 256; i++) {
            char cur = (char)i;
            if(map[i] % 2 != 0) {
                if(!single) {
                    single = true;
                    singleChar = cur+"";
                }else
                    return res;
            }
            for(int j = 0; j < map[i]/2; j++)
                half[p++] = cur;
        }
        boolean[] used = new boolean[len/2];
        dfsGenerate(half, res, singleChar, used, new char[len/2], 0);
        return res;
    }
    
    public void dfsGenerate(char[] half, List<String> res, String singleChar, boolean[] used, char[] cur, int p) {
        if(p == half.length) {
            StringBuilder tmp = new StringBuilder(String.valueOf(cur));
            res.add(tmp.toString() + singleChar + tmp.reverse().toString());
            return;
        }
        
        for(int i = 0; i < half.length; i++) {
            if(used[i])
                continue;
            if(i != 0 && half[i] == half[i-1] && !used[i-1])
                continue;
            used[i] = true;
            cur[p] = half[i];
            dfsGenerate(half, res, singleChar, used, cur, p+1);
            used[i] = false;
        }
    }
    

    }


Log in to reply
 

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