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 []
.public class Solution {
public List<String> generatePalindromes(String s) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
Character odd = null;
for (Character c : map.keySet()) {
int num = map.get(c);
if (num % 2 == 1) {
if (odd != null) return new ArrayList<String>();
else {
odd = c;
map.put(c, num - 1);
}
}
}
String cur = odd == null ? "" : Character.toString(odd);
List<String> strs = new ArrayList<String>();
helper(map, cur, strs, s.length());
return strs;
}
private void helper(HashMap<Character, Integer> map, String cur, List<String> res, int len) {
if (cur.length() == len) {
res.add(cur);
} else {
for (Character c : map.keySet()) {
if (map.get(c) == 0) {
continue;
}
int val = map.get(c);
map.put(c, val - 2);
helper(map, c + cur + c, res, len);
map.put(c, val);
}
}
}
}
没有评论:
发表评论