1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
public List<String> generatePalindromes(String s) {
int[] charCount = new int[26];
int oddCount = 0;
for (char letter : s.toCharArray()) {
charCount[letter - 'a'] += 1;
if (charCount[letter - 'a'] % 2 == 1) {
oddCount += 1;
} else {
oddCount -= 1;
}
}
if (oddCount > 1) {
return new ArrayList<>();
}
String oddLetter = "";
List<Character> candidates = new ArrayList<>();
for (int i = 0; i < charCount.length; i++) {
char currLetter = (char) (i + 'a');
if (charCount[i] % 2 != 0) {
oddLetter = String.valueOf(currLetter);
charCount[i] -= 1;
}
for (int j = 0; j < charCount[i] / 2; j++) {
candidates.add(currLetter);
}
}
List<String> ans = new ArrayList<>();
dfs(ans, candidates, new StringBuilder(), new boolean[candidates.size()], oddLetter);
return ans;
}
private void dfs(List<String> ans, List<Character> candidates, StringBuilder curr, boolean[] used, String mid) {
if (curr.length() == candidates.size()) {
ans.add(curr.toString() + mid + curr.reverse().toString());
curr.reverse();
return;
}
for (int i = 0; i < candidates.size(); i++) {
if (used[i] || (i > 0 && candidates.get(i) == candidates.get(i - 1) && !used[i - 1])) {
continue;
}
curr.append(candidates.get(i));
used[i] = true;
dfs(ans, candidates, curr, used, mid);
used[i] = false;
curr.setLength(curr.length() - 1);
}
}
}
|
先统计每个字母出现的频率, 看出现奇数次letter的个数是否大于1, 如果是, 那就组不成palindrome, 不是的话继续下面的操作. 然后我们统计palindrome一侧可以出现哪些字母. 这里需要注意的是, 出现奇数次的letter(如果有的话)虽然中间是它, 但是它也是可以出现在一侧的, 并且有可能出现多次, 我们有时候会默认出现奇数次的letter只在中间出现, 这是不对的, 这样默认它只出现一次, 但是实际上可能是多次. 然后我们开始用backtrack. 在某个位置, 我们从到到尾遍历, 挑一个字符出现在当前的位置, 之前选中的无法再选, 还有就是如果之前某个字母在在这一层被选择了, 它就不能再次被选. 第一种情况好说, 用一个boolean数组, 记录每个位置的字符是否已经被选中放进了StringBuilder中. 第二种情况如何判断? 由于我们是从0到尾挨个让没有被选中的字母坐当前的位置, 于是如果某个字母之前被选择过在这里, 并且它在candidates中也是出现多次, 由于我们放letter进candidates中时, 相同letter都是挨着的, 于是当我们发现当前字母和之前一个字母一样, 并且之前字母没有被选中, 这就说明上一个字母坐过当前的位置(没有被选中说明上一个字母是可以在这一层被选中, 并且它有出现在前一个位置, 因此它在当前层之前被选中过), 因此我们就跳过此时的字母, 避免重复计算. 这个方法很妙.
时间复杂度和空间复杂度不好求.
