Problem:
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 [].
Analysis:
This problem is very easy, it shares the same idea with "Strobogrammatic Number".
Use the rule you check a "Palindrome Permutation" to construct it!!! (two pointer!) I have made one mistake in implementation.
Forget that when "len == 1", the string must a pilindrome string! Wrong part:
if (len <= 1) {
return ret;
} Errors:
Input:
"a"
Output:
[]
Expected:
["a"]
Solution:
public class Solution {
public List<String> generatePalindromes(String s) {
if (s == null)
throw new IllegalArgumentException("s is null");
List<String> ret = new ArrayList<String> ();
int len = s.length();
if (len == 0) {
return ret;
}
HashMap<Character, Integer> map = new HashMap<Character, Integer> ();
for (char c : s.toCharArray()) {
if (map.containsKey(c))
map.put(c, map.get(c)+1);
else
map.put(c, 1);
}
int odd_count = 0;
char odd_char = 'a';
for (char c : map.keySet()) {
if (map.get(c) % 2 == 1) {
odd_count++;
odd_char = c;
}
}
if (odd_count >= 2)
return ret;
if (odd_count == 1) {
searchPath(map, odd_char + "", len, ret);
} else{
searchPath(map, "", len, ret);
}
return ret;
}
private void searchPath(HashMap<Character, Integer> map, String cur, int target, List<String> ret) {
String new_cur = cur;
int len = new_cur.length();
if (len == target) {
ret.add(new_cur);
return;
}
for (char c : map.keySet()) {
if (map.get(c) >= 2) {
new_cur = c + cur + c;
map.put(c, map.get(c) - 2);
searchPath(map, new_cur, target, ret);
map.put(c, map.get(c) + 2);
}
}
}
}