Short backtracking solution in Java (3 ms)


  • 26
    L

    We only need to generate the first part of palindrome string, and the remaining part will be a middle character with the reverse of first part.

    private List<String> list = new ArrayList<>();
    
    public List<String> generatePalindromes(String s) {
        int numOdds = 0; // How many characters that have odd number of count
        int[] map = new int[256]; // Map from character to its frequency
        for (char c: s.toCharArray()) {
            map[c]++;
            numOdds = (map[c] & 1) == 1 ? numOdds+1 : numOdds-1;
        }
        if (numOdds > 1)   return list;
        
        String mid = "";
        int length = 0;
        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                if ((map[i] & 1) == 1) { // Char with odd count will be in the middle
                    mid = "" + (char)i;
                    map[i]--;
                }
                map[i] /= 2; // Cut in half since we only generate half string
                length += map[i]; // The length of half string
            }
        }
        generatePalindromesHelper(map, length, "", mid);
        return list;
    }
    private void generatePalindromesHelper(int[] map, int length, String s, String mid) {
        if (s.length() == length) {
            StringBuilder reverse = new StringBuilder(s).reverse(); // Second half
            list.add(s + mid + reverse);
            return;
        }
        for (int i = 0; i < 256; i++) { // backtracking just like permutation
            if (map[i] > 0) {
                map[i]--;
                generatePalindromesHelper(map, length, s + (char)i, mid);
                map[i]++;
            } 
        }
    }

  • 0
    Y

    Hi lianngg, nice solution! Yet I found that the main speed gain comes from assuming that the chars are ascii. Otherwise the running time would be 11ms... what a difference.


  • 1
    S

    Same idea but improve a bit on the backtracking part.

    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> res = new ArrayList<>();
            int odd = 0;
            String mid = "";
            int []hash = new int[256];
            int length = 0; 
            for(int i=0; i<s.length(); i++){
                hash[s.charAt(i)]++;
            }
    
            for(int i=0; i<256; i++){
                if(hash[i] > 0){
                    if(hash[i] % 2 != 0){
                        odd++;
                        if (odd > 1) return new LinkedList<String>();
                        mid = String.valueOf((char)i);
                        hash[i]--;
                    }
                    hash[i] /= 2;
                    length += hash[i];
                }
            }
            
            backtrack(res, hash, new StringBuffer(), mid, length);
            return res;
        }
        
        void backtrack(List<String> res, int[] hash, StringBuffer sb, String mid, int length){
            if (sb.length() == length){
                res.add(sb.toString() + mid + sb.reverse().toString());
                sb.reverse();
                return;
            }
            
            for(int i=0; i<256; i++){
                if(hash[i] > 0){
                    hash[i]--;
                    sb.append((char)i);
                    backtrack(res, hash, sb, mid, length);
                    sb.deleteCharAt(sb.length() -1);
                    hash[i]++;
                }
            }
            
        }
    }
    

  • 0
    M

    said in Short backtracking solution in Java (3 ms):

    numOdds = (map[c] & 1) == 1 ? numOdds+1 : numOdds-1;

    Nice trick!


  • 1
    V

    Nice solution!
    One question here, why we don't need the duplicate check like we did for Permutation II here? How to ensure there is no duplicate string s?

    for (int i = 0; i < 256; i++) { // backtracking just like permutation
    if (map[i] > 0) {
    map[i]--;
    generatePalindromesHelper(map, length, s + (char)i, mid);
    map[i]++;
    }
    }


  • 0
    E

    Wow that's a clear solution!
    I think length can be got directly from "(s.length() - mid.length()) / 2" and don't need to count it in for loop


  • 0
    H

    @lianngg
    One question here, why we don't need the duplicate check like we did for Permutation II here? How to ensure there is no duplicate string s?


  • 0
    P

    @Vickyer
    @hugo525

    for (int i = 0; i < 256; i++) { // backtracking just like permutation
    if (map[i] > 0) {
    map[i]--;
    generatePalindromesHelper(map, length, s + (char)i, mid);
    map[i]++;
    }
    }

    the total number of map[i] (i from 0 to 256) is fixed, so one element only used once, this avoids duplicate like [a,a,a] if the map indicates a string [a,c(1),c(2)]. Also in each stack of recursion this for loop goes from 0 to 255, and the map is updated each time, this avoids duplicates like [a, c(1), c(2)] and [a, c(2), c(1)].


Log in to reply
 

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