1ms 99% Concise Java Sol.


  • 0
    O
    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> ans = new LinkedList();
            
            int[] cnt = new int[128];
            char[] ch = s.toCharArray();
            for (char c : ch) cnt[c]++;
            char single = (char) 0;
            int pivot = 0;
            for (char c = 1; c < 128; c++) {
                if (cnt[c] % 2 == 1) {
                    if (single > 0) return ans;
                    single = c;
                }
                if (cnt[c] / 2 > 0)
                    for (; cnt[c] > 1; cnt[c] -= 2)
                        ch[pivot++] = c;
            }
            find(0, pivot, ch, ans, single);
            return ans;
        }
        
        private void find(int pos, int piv, char[] arr, List<String> ans, char single) {
            if (pos >= piv - 1) {
                int j = piv;
                if (single > 0) arr[j++] = single;
                for (int i = piv - 1; i >= 0; i--) arr[j++] = arr[i];
                ans.add(new String(arr));
                return;
            }
            
            char t = arr[pos];
            for (int i = pos; i < piv; i++) 
                if (i == pos || arr[i] != arr[pos]) {
                arr[pos] = arr[i];
                arr[i] = t;
                find(pos + 1, piv, arr, ans, single);
                arr[i] = arr[pos];
            }
            arr[pos] = t;
        }
    }
    

Log in to reply
 

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