Java 1ms beats 99.67%


  • 5
    J

    I'm generating permutations on the left side of the string, then constantly copying characters to the right side to maintain the palindrome.

    There are lots of comments in the code, but please ask if there is anything that is unclear.

    public class Solution {
        
        List<String> results;
        
        char[] chars;
        
        int lengthMinusOne, halfLength;
        
        public List<String> generatePalindromes(String s) {
            
            results = new ArrayList<String>();
            
            // We will be generating permutations in place.
            chars = s.toCharArray();
            int length = chars.length;
            
            // Return no result for empty string.
            if(length == 0) return results;
            
            // Sort the array to bring duplicates together.
            Arrays.sort(chars);
            // The array now looks like aabbcdd
            
            // Precompute a few values for performance. 
            lengthMinusOne = length - 1;
            halfLength = length / 2; 
            
            // Prepare the first half of the string. It will contain
            // a single character from each pair. The middle character
            // is placed in the middle.
            // When done, the array will look like abdc***
            boolean foundMiddle = false;
            
            for(int readCursor = 0, writeCursor = 0; readCursor < length; readCursor++){
                char c = chars[readCursor];
                
                // Check for pair of characters.
                if(readCursor < lengthMinusOne && c == chars[readCursor+1]){
                    
                    // Found pair. Write one of them to the left of the string.
                    chars[writeCursor++] = c;
                    readCursor++;
                
                }else{
                    
                    // Found isolated character. Make sure this is the only one
                    // so far, and check that the string length is odd.
                    if(!foundMiddle && (chars.length & 1) == 1){
                        
                        // Place the middle character.
                        foundMiddle = true;
                        chars[chars.length / 2] = c;
                        
                    }else{
    
                        // Can't make palindromes from this string.
                        return results;
                    }
                }
            }
            
            // Generate permutations for all characters.
            generate(0);
            
            return results;
        }
    
        // Generates permutations by swapping characters.
        void generate(int start){
            
            // When we run out of characters, add the result to the list.
            if(start == halfLength){
                results.add(new String(chars));
                return;
            }
    
            // Swap each character into place.
            char prev = 0;
            for(int i=start; i<halfLength; i++){
                
                // Check for duplicates.
                if(prev == chars[i]) continue;
                prev = chars[i];
                
                // Place one character.
                swap(start,i);
                
                // Generate permutations for remaining characters.
                generate(start+1);
                
                // Return the character to it's position.
                swap(start,i);
            }
        }
    
        // Swap maintains the palindrome by mirroring chars on the right side.
        void swap(int a, int b){
            char temp = chars[a];
            
            // Place at a on left side of palindrome.
            chars[a] = chars[b];
            
            // Place matching char on right side.
            chars[lengthMinusOne - a] = chars[b];
            
            // Place left.
            chars[b] = temp;
            
            // Place right.
            chars[lengthMinusOne - b] = temp;
        }
    }

  • 1
    O

    nice work. For me I did bucket sort of the string to scan out the letters (cand, short for candidates) for palindrome construction. 1ms 99.67%. Yours is better.

    public class Solution {
        public List<String> generatePalindromes(String str) {
            char[] s = str.toCharArray();
            char[] cand = init(s);
            if (cand == null) return new ArrayList();
            int len = cand.length;
            List<String> ans = new ArrayList();
            dfs(0, cand, ans);
            return ans;
        }
        
        private char[] init(char[] s) {
            int[] b = new int[128]; // bucket for sorting
            int odd = 0, j = 0, cnt = 0;
            for (char c : s)
                if (b[c]++ % 2 == 1) cnt++;
            
            char[] ch = new char[cnt + 1]; // cnt + 1th element is to mark element that appears odd times
            for (int i = 0; i < b.length; i++) {
                while (b[i] > 1) {
                    ch[j++] = (char)i;
                    b[i] -= 2;
                }
                if (b[i] > 0) {
                    if (odd != 0) return null; else odd = i;
                }
            }
            ch[j++] = (char)odd; 
            return ch;
        }
        
        private void dfs(int from, char[] cand, List<String> ans) {
            int n = cand.length - 1; 
            if (from == n) {
                add(cand, ans);
                return;
            }
            for (int i = from; i < n; i++) // avoid repeating
                if (i == from || (cand[i] != cand[from] && cand[i] != cand[i - 1])) {
                    xwap(from, i, cand); 
                    dfs(from + 1, cand, ans);
                    xwap(from, i, cand);
                }
        }
        
        private void xwap(int i, int j, char[] a) {
            char t = a[i]; a[i] = a[j]; a[j] = t;
        }
        
        private void add(char[] cand, List<String> ans) {
            int len = cand.length - 1;
            int m = (cand[len] == (char)0) ? 2 * len : 2 * len + 1;
            char[] ch = new char[m];
            for (int i = 0, j = m - 1; i <= j; ch[j--] = cand[i], ch[i] = cand[i++]);
            ans.add(String.valueOf(ch));
        }
    }

  • 0
    Z

    This code is incorrect for new test case "aaaabbbbcccc"


  • 0
    Q

    @zestypanda I think they just in different order. The code works.


  • 0
    Z

    @QMZSJMFS I don't know whether that's the case. I copied the code, and it failed for this test case for some reason I don't know.


  • 0
    Q

    @zestypanda I don't know, too. I never saw this kind of problem before.


Log in to reply
 

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