题目：
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.
- To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.
链接： http://leetcode.com/problems/palindrome-permutation-ii/
题解：
求一个字符串能生成的all palindromic permutaitons。这个题目又写得很长。 总的来说我们要考虑以下一些点:
- 给定s是否能生成Palindrome
- 生成的Palindrome的奇偶性，是奇数的话中间的字符是哪一个
- 利用permutation II的原理，计算左半部string
- 根据Palindrome的奇偶性判断是否要加上中间的独立字符
- 根据计算出的左半部string，计算右半部string，合并，加入到结果集中
- 复杂度的计算(留给二刷了)
Time Complexity - O(2n)， Space Complexity - O(2n)
public class Solution {
private boolean isOddPalindrome;
private String singleChar;
public List<String> generatePalindromes(String s) {
List<String> res = new ArrayList<>();
String evenPalindromeString = generateEvenPalindromeString(s);
if(evenPalindromeString.length() == 0) {
if(this.isOddPalindrome)
res.add(singleChar);
return res;
}
char[] arr = evenPalindromeString.toCharArray();
Arrays.sort(arr);
StringBuilder sb = new StringBuilder();
boolean[] visited = new boolean[arr.length];
generatePalindromes(res, sb, arr, visited);
return res;
}
private void generatePalindromes(List<String> res, StringBuilder sb, char[] arr, boolean[] visited) {
if(sb.length() == arr.length) { // we only get permutation of left part of the result palindrome
String s = sb.toString();
res.add(this.isOddPalindrome ? (s + this.singleChar + reverse(s)) : (s + reverse(s)) );
return;
}
for(int i = 0; i < arr.length; i++) {
if(visited[i] || (i > 0 && arr[i] == arr[i - 1] && !visited[i - 1])) { //skip duplicate
continue;
}
if(!visited[i]) {
visited[i] = true;
sb.append(arr[i]);
generatePalindromes(res, sb, arr, visited);
sb.setLength(sb.length() - 1);
visited[i] = false;
}
}
}
private String reverse(String s) { //reverse string
char[] arr = s.toCharArray();
int lo = 0, hi = s.length() - 1;
while(lo < hi) {
char c = arr[lo];
arr[lo++] = arr[hi];
arr[hi--] = c;
}
return String.valueOf(arr);
}
private String generateEvenPalindromeString(String s) { // get even chars of palindrome
Set<Character> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(set.contains(c)) {
set.remove(c);
sb.append(c); // append only even counted chars
} else {
set.add(c);
}
}
if(set.size() <= 1) {
if(set.size() == 1) {
for(char chr : set) {
this.singleChar = String.valueOf(chr);
}
this.isOddPalindrome = true;
}
return sb.toString();
} else {
return "";
}
}
}
Reference:
https://leetcode.com/discuss/53626/ac-java-solution-with-explanation