05 August 2008
给定一个字符串 s，返回它的所有回文排列（没有重复）。
您可以按任何顺序返回答案。如果 s 没有回文排列，则返回一个空列表。
Backtracking
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
52
53
54
55
56
57
58
59
60
class Solution {
public List<String> generatePalindromes(String s) {
int[] dict = new int[256];
for (char c : s.toCharArray()) {
dict[c]++;
}
int odd = 0;
for (int n : dict) {
if (n % 2 == 1) {
odd++;
}
}
if (odd > 1) return new ArrayList<String>();
List<Character> list = new ArrayList<Character>();
Character ch = null;
for (int i = 0; i < 128; i++) {
if (dict[i] % 2 == 1) {
ch = (char) (i);
}
for (int j = 0; j < dict[i] / 2; j++) {
list.add((char) (i));
}
}
List<String> res = new ArrayList<>();
dfs(list, res, 0, new char[s.length()], ch, new boolean[list.size()], s.length());
return res;
}
public void dfs(List<Character> chars, List<String> result, int ind, char[] arr, Character ch, boolean[] visited, int len) {
if (ind == len / 2) {
if (ch == null) {
result.add(new String(arr));
} else {
arr[ind] = ch;
result.add(new String(arr));
}
return;
}
for (int i = 0; i < chars.size(); i++) {
if (visited[i]) {
continue;
}
if (i > 0 && chars.get(i) == chars.get(i - 1) && !visited[i - 1]) {
continue;
}
arr[ind] = chars.get(i);
arr[len - 1 - ind] = chars.get(i);
visited[i] = true;
dfs(chars, result, ind + 1, arr, ch, visited, len);
visited[i] = false;
}
}
}