267. Palindrome Permutation II

Link

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example 1:

Input: "aabb"
Output: ["abba", "baab"]

Example 2:

Input: "abc"
Output: []

Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.

2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

Solution

*這題要列舉所有可能，看來用回朔法(backTrace)比較適合 *需先把沒有解的狀況排除，可以幫助choose，ex. 出現奇數次數的字元有兩個以上，空字串。 計算次數透過hashMap<Character, Integer>。 考慮奇數跟偶數長度組合 若是奇數次數的字元有一個。那並定是在中間，且長度會是奇數:ex aabaa, scasacs 需要額外考慮奇數的tempString內容。 若是偶數一開始為空字串，若是奇數一開始為奇數次數字元，並更新hashMap。 設計helper 有以上理解之後，就可以開始設計helper，首先我們知道回文的特性是左右兩邊剛好是倒過來的關係。所以只有列舉一半。另一半可以透過reverse生成。 1. Choose - > 確認每個字元的count >= 2時，可以choose，拿取之後hashMap裡的count數要-2 2. Observe -> 更新完count之後的hashMap帶入下一次iteration 3. Unchoose -> undo choose，hashMap裡的count數+2

分支完成的條件:

需要考慮奇數跟偶數長度的palindrome (目前的len等於target len/2)。 此時要加入reverse後的另一半。

    public static List<String> generatePalindromes(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int odd = 0;
        char mid = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if ((entry.getValue() % 2 == 1)) {
                odd++;
                mid = entry.getKey();
            }
        }
        if (odd > 1 || s == null || s.length() == 0) {
            return new ArrayList<String>();
        }
        ArrayList<String> ret = new ArrayList<>();
        String temp = (odd == 1) ? "" + mid : "";
        if(mid != 0){
            map.put(mid, map.get(mid) - 1);
        }
        helper(map, ret, temp, (s.length() +1 ) / 2, (odd == 1));
        return ret;
    }

    public static void helper(HashMap<Character, Integer> map, ArrayList<String> finalResult, String tempResult, int len, boolean isOdd) {
        if (tempResult.length() == len){
            StringBuilder sb = new StringBuilder(tempResult);
            if(isOdd){
                sb.reverse().deleteCharAt(0).append(tempResult);
                tempResult = tempResult.substring(len-1);
            }else{
                sb.reverse().append(tempResult);
                tempResult = "";
            }
            finalResult.add(sb.toString());
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()){
            if(entry.getValue() != 0){
                //choose
                int value = entry.getValue();
                map.put(entry.getKey(), value - 2);
                tempResult = entry.getKey() + tempResult;

                //observe
                helper(map, finalResult, tempResult, len, isOdd);

                //un-choose
                map.put(entry.getKey(), value);
                tempResult = tempResult.substring(1);
            }
        }
    }