2ms fast Java solution beats 96.7% using backtracking permutation


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

    }


Log in to reply
 

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