backtracking solution: easy understanding, efficient, only permutate half length of the string


  • 0
    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> result = new LinkedList<>();
            Map<Character, Integer> map = new HashMap<>();
            for(char c:s.toCharArray()){
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            char[] chars = new char[map.size()];
            int[] count = new int[map.size()];
            char[] res = new char[s.length()];
            
            int evenCnt = 0;
            int oddCnt = 0;
            int oddi = 0;
            int i = 0;
            for(Map.Entry<Character, Integer> entry:map.entrySet()){
                char c = (char)entry.getKey();
                int cnt = (int)entry.getValue();
                chars[i] = c;
                count[i] = cnt;
                if(cnt % 2 == 0) evenCnt++;
                if(cnt % 2 == 1) {
                    oddCnt++;
                    oddi = i;
                }
                i++;
            }
            if(evenCnt == map.size()){
                backtrack(s, chars, count, 0, res, result);
            }else if(oddCnt == 1 && evenCnt == map.size()-1){
                res[s.length()/2] = chars[oddi];
                count[oddi]--;
                backtrack(s, chars, count, 0, res, result);
            }
            return result;
        }
        
        private void backtrack(String s, char[] chars, int[] count, int level, char[] res, List<String> result){
            if(level == s.length()/2){
                String str = new String(res);
                result.add(str);
                return ;
            }
            for(int i = 0; i < chars.length; i++){
                if(count[i] == 0) continue;
                if(count[i] % 2 == 0){
                    count[i] -= 2;
                    res[level] = chars[i];
                    res[res.length-level-1] = chars[i];
                    backtrack(s, chars, count, level+1, res, result);
                    count[i] += 2;
                }
            }
        }
    }
    

Log in to reply
 

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