8000 refactor 267 · hiradha/Leetcode@5efa888 · GitHub
[go: up one dir, main page]
Skip to content 10000

Commit 5efa888

Browse files
fishercoder1534fishercoder1534
committed
refactor 267
1 parent 63bfe56 commit 5efa888

File tree

1 file changed

+54
-67
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+54
-67
lines changed

‎src/main/java/com/fishercoder/solutions/_267.java

Lines changed: 54 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -5,87 +5,74 @@
55
import java.util.List;
66
import java.util.Map;
77

8-
/**
9-
* Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
10-
11-
For example:
12-
13-
Given s = "aabb", return ["abba", "baab"].
14-
15-
Given s = "abc", return [].
16-
17-
Hint:
18-
19-
If a palindromic permutation exists, we just need to generate the first half of the string.
20-
To generate all distinct permutations of a (half of) string, use a similar approach from: _46 II or Next Permutation.
21-
*/
228
public class _267 {
239

24-
public List<String> generatePalindromes(String s) {
25-
int odd = 0;
26-
String mid = "";
27-
List<String> res = new ArrayList();
28-
List<Character> list = new ArrayList();
29-
Map<Character, Integer> map = new HashMap();
30-
31-
// step 1. build character count map and count odds
32-
for (int i = 0; i < s.length(); i++) {
33-
char c = s.charAt(i);
34-
map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
35-
odd += map.get(c) % 2 != 0 ? 1 : -1;
36-
}
10+
public static class Solution1 {
11+
public List<String> generatePalindromes(String s) {
12+
int odd = 0;
13+
String mid = "";
14+
List<String> res = new ArrayList();
15+
List<Character> list = new ArrayList();
16+
Map<Character, Integer> map = new HashMap();
17+
18+
// step 1. build character count map and count odds
19+
for (int i = 0; i < s.length(); i++) {
20+
char c = s.charAt(i);
21+
map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
22+
odd += map.get(c) % 2 != 0 ? 1 : -1;
23+
}
3724

38-
// cannot form any palindromic string
39-
if (odd > 1) {
40-
return res;
41-
}
25+
// cannot form any palindromic string
26+
if (odd > 1) {
27+
return res;
28+
}
4229

43-
// step 2. add half count of each character to list
44-
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
45-
char key = entry.getKey();
46-
int val = entry.getValue();
30+
// step 2. add half count of each character to list
31+
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
32+
char key = entry.getKey();
33+
int val = entry.getValue();
4734

48-
if (val % 2 != 0) {
49-
mid += key;
50-
}
35+
if (val % 2 != 0) {
36+
mid += key;
37+
}
5138

52-
for (int i = 0; i < val / 2; i++) {
53-
list.add(key);
39+
for (int i = 0; i < val / 2; i++) {
40+
list.add(key);
41+
}
5442
}
55-
}
5643

57-
// step 3. generate all the permutations
58-
getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);
44+
// step 3. generate all the permutations
45+
getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);
5946

60-
return res;
61-
}
62-
63-
// generate all unique permutation from list
64-
void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb,
65-
List<String> res) {
66-
if (sb.length() == list.size()) {
67-
// form the palindromic string
68-
res.add(sb.toString() + mid + sb.reverse().toString());
69-
sb.reverse();
70-
return;
47+
return res;
7148
}
7249

73-
for (int i = 0; i < list.size(); i++) {
74-
// avoid duplication
75-
if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) {
76-
continue;
50+
// generate all unique permutation from list
51+
void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb,
52+
List<String> res) {
53+
if (sb.length() == list.size()) {
54+
// form the palindromic string
55+
res.add(sb.toString() + mid + sb.reverse().toString());
56+
sb.reverse();
57+
return;
7758
}
7859

79-
if (!used[i]) {
80-
used[i] = true;
81-
sb.append(list.get(i));
82-
// recursion
83-
getPerm(list, mid, used, sb, res);
84-
// backtracking
85-
used[i] = false;
86-
sb.deleteCharAt(sb.length() - 1);
60+
for (int i = 0; i < list.size(); i++) {
61+
// avoid duplication
62+
if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) {
63+
continue;
64+
}
65+
66+
if (!used[i]) {
67+
used[i] = true;
68+
sb.append(list.get(i));
69+
// recursion
70+
getPerm(list, mid, used, sb, res);
71+
// backtracking
72+
used[i] = false;
73+
sb.deleteCharAt(sb.length() - 1);
74+
}
8775
}
8876
}
8977
}
90-
9178
}

0 commit comments

Comments
 (0)
0