Java solution using character count map and backtracking


  • 0
    Y

    Basic idea: get character and character count map first, and use backtracking recursion method to generate first half.

    public List<String> generatePalindromes(String s) {
        Map<Character, Integer> map = generateCharMap(s);
        List<String> palindromes = new ArrayList<String>();
        if (!isPalindrome(map)) {
            return palindromes;
        }
        int n = s.length();
        if (n == 1) {
            palindromes.add(s);
            return palindromes;
        }
        boolean isOdd = n % 2 == 1;
        char[] letters = generateChars(map, n/2);
        List<String> half = new ArrayList<String>();
        generateHalf(letters, 0, new StringBuilder(), half);
        char oddLetter = '0';
        if (isOdd) {
            oddLetter = getOdd(map);
        }
        for (String h : half) {
            palindromes.add(generateString(h, isOdd, oddLetter));
        }
        return palindromes;
    }
    
    private Map<Character, Integer> generateCharMap(String s) {
        int n = s.length();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
        }
        return map;
    }
    
    private boolean isPalindrome(Map<Character, Integer> map) {
        int oddCnt = 0;
        for (char c : map.keySet()) {
            if (map.get(c) % 2 == 1) {
                oddCnt += 1;
                if (oddCnt > 1) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private char[] generateChars(Map<Character, Integer> map, int charCount) {
        char[] chars = new char[charCount];
        int i = 0;
        for (char c : map.keySet()) {
            int cnt = map.get(c);
            while (cnt > 1) {
                chars[i] = c;
                i++;
                cnt -= 2;
            }
        }
        return chars;
    }
    
    private void generateHalf(char[] letters, int start, StringBuilder sb, List<String> half) {
        int n = letters.length;
        if (start == n) {
            half.add(sb.toString());
            return;
        }
        for (int i = start; i < n; i++) {
            if (i == start || letters[i] != letters[i-1]) {
                swap(letters, i, start);
                sb.append(letters[start]);
                generateHalf(letters, start+1, sb, half);
                sb.deleteCharAt(sb.length()-1);
                swap(letters, i, start);
            }
        }
    }
    
    private char getOdd(Map<Character, Integer> map) {
        for (char c : map.keySet()) {
            if (map.get(c) % 2 == 1) {
                return c;
            }
        }
        return '0';
    }
    
    private String generateString(String half, boolean isOdd, char oddLetter) {
        StringBuilder sb = new StringBuilder(half);
        String reverse = new StringBuilder(half).reverse().toString();
        if (isOdd) {
            sb.append(oddLetter);
        }
        sb.append(reverse);
        return sb.toString();
    }
    
    private void swap(char[] letters, int position1, int position2) {
        if (position1 == position2) {
            return;
        }
        char tmp = letters[position1];
        letters[position1] = letters[position2];
        letters[position2] = tmp;
    }

Log in to reply
 

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