首页 > 代码库 > 267. Palindrome Permutation II
267. Palindrome Permutation II
Given a string s
, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
For example:
Given s = "aabb"
, return ["abba", "baab"]
.
Given s = "abc"
, return []
.
Hint:
- If a palindromic permutation exists, we just need to generate the first half of the string.
本题难度系数很难,看了答案实现起来仍然出了不少错误。我开始想的是按照Permutations II的方法来做,找到后再进行筛选,选出满足palindrome 条件的数,实现起来比较麻烦,而且最后给出了内存不足,故打断了这种想法。
看了discussion,首先,做一个hashmap,key存储字符,value存储出现的次数,用odd表示odd-even后还剩下多少个odd,如果大于1,那么就不是palindrome,结果就是空的。然后把出现偶数次数的字符以value/2的次数存储在list里面,把出现单独次数的字符存储在mid里面。然后把list按照Permutations II的方法进行回溯,结果就可以做出来了。需要注意的是,Stringbuilder,reverse之后一定要reverse回来,代码如下:
1 public class Solution { 2 public List<String> generatePalindromes(String s) { 3 List<String> res = new ArrayList<String>(); 4 String mid = ""; 5 List<Character> list = new ArrayList<Character>(); 6 Map<Character,Integer> map = new HashMap<Character,Integer>(); 7 int odd = 0; 8 for(char c:s.toCharArray()){ 9 map.put(c,map.containsKey(c)?map.get(c)+1:1); 10 odd=odd+(map.get(c)%2==1?1:-1); 11 } 12 if(odd>1) return res; 13 for(Map.Entry<Character,Integer> entry:map.entrySet()){ 14 char key = entry.getKey(); 15 int val = entry.getValue(); 16 if(val%2==1) mid=mid+key; 17 for(int i=0;i<val/2;i++){ 18 list.add(key); 19 } 20 } 21 backtracking(res,mid,list,new StringBuilder(),new boolean[list.size()]); 22 return res; 23 } 24 public void backtracking(List<String> res,String mid,List<Character> list,StringBuilder sb,boolean[] used){ 25 if(sb.length()==list.size()){ 26 res.add(sb.toString()+mid+sb.reverse().toString()); 27 sb.reverse(); 28 }else{ 29 for(int i=0;i<list.size();i++){ 30 if(used[i]||i>0&&list.get(i)==list.get(i-1)&&!used[i-1]) continue; 31 used[i] = true; 32 sb.append(list.get(i)); 33 backtracking(res,mid,list,sb,used); 34 used[i] = false; 35 sb.deleteCharAt(sb.length()-1); 36 } 37 } 38 } 39 }
267. Palindrome Permutation II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。