产生input中 所有permutation 中符合 palindrome 的。 Input: "aabb"Output: ["abba", "baab"] 分析： 和47. Permutations II 本质上一样的，首先字母有重复的，因此为了避免重复解，得先排序。 47题example

Input: [1,1,2]Output:[  [1,1,2],  [1,2,1],  [2,1,1]]

 然而写了一个类似47的解竟然TLE了，

优化策略1. 统计整个字符串中每个字母的个数，如果奇数个的个数>1 ，则所有的permutation 都不可能符合要求。 

做了这个优化后写了如下code, 但时间复杂度太高，排到了 0.0%了吧，算法复杂度为o(n!)

1 class Solution { 2     public List
      
        generatePalindromes(String s) { 3         List
       
         result = new ArrayList<>(); 4         int[] map = new int[128]; 5         if (!canPermutePalindrome(s, map)) 6             return new ArrayList < > (); 7         char[] ch = s.toCharArray(); 8         Arrays.sort(ch); 9         dfs(new StringBuilder(), result, ch,new boolean[s.length()]);10         return result;11     }12     13     private void dfs(StringBuilder curResult, List
        
          result, char[] ch, boolean[] used){14         if(curResult.length() == ch.length){15             //System.out.println(curResult);16             String candid = curResult.toString();17             if(isPalindromes(candid)){18                 result.add(candid);19             }20             return;21         }22         23         for(int i=0; i
         
          0 && ch[i] == ch[i-1] && !used[i-1]) continue;25            26                 curResult.append(ch[i]);27                 used[i] = true;28                 dfs(curResult,result,ch,used);29                 curResult.setLength(curResult.length()-1);30                 used[i] = false;31             32         }33     }34     35     private boolean isPalindromes(String s){36         int len = s.length();37         for(int i=0; i
         
        
       
      

看了 solution 里的优化方法， 可以优化到 o(n/2!) 而不是 o(n!) 每次只要build 一半的字符串就够了。