• palindrome中，字符均是成对出现的（除了当字符串长度是单数时的中间字母）
• 创建一个set对象
• 遍历字符串，当遇到一个字符的时候检测set中有没有该字符。
  • 如果有则将该字符从set中删除
  • 否则，将该字符添加到set中
• 最后检测set中元素的个数
  • 个数小于等于1时，说明满足条件。

Implementation

public class Solution {    public boolean canPermutePalindrome(String s) {        HashSet
    
      set = new HashSet
     
      ();        for (int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if (!set.add(c)) { // if the set contains c, add() will return false                set.remove(c);            }        }        return set.size() <= 1;    }}
     
    

• 使用Palindrome Permutation的方法判断给定的字符串是否可以构造palindrome字符串
• 选择构造palindrome一半所需要的字符和mid字符
• 产生permutation

Implementation

public class Solution {    public List
    
      generatePalindromes(String s) {        ArrayList
     
       charList = new ArrayList
      
       ();        HashSet
       
         set = new HashSet
        
         ();        for (int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if (!set.add(c)) {                set.remove(c);                charList.add(c);            }        }        Collections.sort(charList);        List
         
           result = new ArrayList
          
           (); if (set.size() > 1) { return result; } // 使用iterator遍历set Iterator
           
             iter = set.iterator(); String mid = ""; if (iter.hasNext()) { mid += iter.next(); } generatePermutations(result, charList, new StringBuilder(), mid); return result; } private void generatePermutations(List
            
              result, ArrayList
             
               charList, StringBuilder sb, String mid) { if (charList.size() == 0) { result.add(sb.toString() + mid + sb.reverse().toString()); sb.reverse(); return; } for (int i = 0; i < charList.size(); i++) { if (i == 0 || charList.get(i) != charList.get(i - 1)) { char c = charList.get(i); sb.append(c); charList.remove(i); generatePermutations(result, charList, sb, mid); sb.deleteCharAt(sb.length() - 1); charList.add(i, c); } } }}
             
            
           
          
         
        
       
      
     
    

Implementation

public class Solution {    public boolean isPalindrome(String s) {        int left = 0;        int right = s.length() - 1;        while (left < right) {            if (Character.isLetterOrDigit(s.charAt(left)) && Character.isLetterOrDigit(s.charAt(right))) {                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))                    return false;                left++;                right--;            }            else {                if (!Character.isLetterOrDigit(s.charAt(left)))                    left++;                if (!Character.isLetterOrDigit(s.charAt(right)))                    right--;            }        }        return true;    }}

• time complexity: n!

Implementation

public class Solution {    public List
    
     
      > partition(String s) {        List
      
       
        > result = new ArrayList
        
         
          >(); List
          
            list = new ArrayList
           
            (); partition(s, 0, list, result); return result; } private void partition(String s, int start, List
            
              list, List
             
              
               > result) { if (start == s.length()) { result.add(new ArrayList
               
                (list)); return; } for (int i = start; i < s.length(); i++) { if (isPalindrome(s, start, i)) { // pay attention to parameter of substring() list.add(s.substring(start, i + 1)); partition(s, i + 1, list, result); list.remove(list.size() - 1); } } } private boolean isPalindrome(String s, int left, int right) { while (left <= right) { if (s.charAt(left) != s.charAt(right)) { return false; } // don't forget move pointers left++; right--; } return true; }}