Skip to content

Commit 64a0e8c

Browse files
author
liwentian
committed
fd
1 parent 0bb6031 commit 64a0e8c

6 files changed

Lines changed: 110 additions & 26 deletions

File tree

‎ebook/Backtracking.tex‎

Lines changed: 29 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1720,27 +1720,46 @@ \subsubsection{Description}
17201720

17211721
\subsubsection{Solution}
17221722
\begin{Code}
1723-
public List<String> generatePalindromes(String s) {
1723+
public static List<String> generatePalindromes(String s) {
17241724
int[] counts = new int[256];
17251725
for (char c : s.toCharArray()) {
17261726
counts[c]++;
17271727
}
1728+
List<String> list = new LinkedList<>();
17281729
StringBuilder sb = new StringBuilder();
1729-
StringBuilder single = new StringBuilder();
1730+
char single = 0;
17301731
for (int i = 0; i < counts.length; i++) {
1731-
int count = counts[i];
1732-
for ( ; count > 1; sb.append((char) i), count -= 2);
1733-
if (count == 1) {
1734-
single.append((char) i);
1732+
if (counts[i] % 2 != 0) {
1733+
if (single != 0) {
1734+
return list;
1735+
}
1736+
single = (char) i;
1737+
counts[i] = ((counts[i] >> 1) << 1);
1738+
}
1739+
for (int j = 0; j < counts[i]; j += 2) {
1740+
sb.append((char)i);
17351741
}
17361742
}
1737-
List<String> result = new LinkedList<String>();
1738-
helper(sb.toString(), single.toString(), result);
1739-
return result;
1743+
1744+
helper(sb, "" + (single != 0 ? single : ""), list);
1745+
return list;
17401746
}
17411747

1742-
private void helper(String s, String t, List<String> list) {
1748+
private static void helper(StringBuilder sb, String cur, List<String> list) {
1749+
if (sb.length() == 0) {
1750+
list.add(cur);
1751+
return;
1752+
}
17431753

1754+
for (int i = 0; i < sb.length(); i++) {
1755+
if (i > 0 && sb.charAt(i) == sb.charAt(i - 1)) {
1756+
continue;
1757+
}
1758+
char c = sb.charAt(i);
1759+
sb.deleteCharAt(i);
1760+
helper(sb, c + cur + c, list);
1761+
sb.insert(i, c);
1762+
}
17441763
}
17451764
\end{Code}
17461765

‎ebook/leetcode.log‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
This is XeTeX, Version 3.14159265-2.6-0.99996 (TeX Live 2016) (preloaded format=xelatex 2017.9.4) 6 SEP 2017 09:21
1+
This is XeTeX, Version 3.14159265-2.6-0.99996 (TeX Live 2016) (preloaded format=xelatex 2017.9.4) 6 SEP 2017 09:52
22
entering extended mode
33
restricted \write18 enabled.
44
%&-line parsing enabled.
@@ -1969,7 +1969,7 @@ File: images/watch.jpg Graphic file (type QTm)
19691969
.
19701970
\FV@Error ...ncyVerb Error:^^J\space \space #1^^J}
19711971

1972-
l.2266 \end{Code}
1972+
l.2285 \end{Code}
19731973

19741974
This error message was generated by an \errmessage
19751975
command, so I can't give any explicit help.
@@ -1982,7 +1982,7 @@ and deduce the truth by order and method.
19821982
.
19831983
\FV@Error ...ncyVerb Error:^^J\space \space #1^^J}
19841984

1985-
l.2300 \end{Code}
1985+
l.2319 \end{Code}
19861986

19871987
(That was another \errmessage.)
19881988

@@ -1994,7 +1994,7 @@ File: images/unlock.png Graphic file (type QTm)
19941994
.
19951995
\FV@Error ...ncyVerb Error:^^J\space \space #1^^J}
19961996

1997-
l.2400 \end{Code}
1997+
l.2419 \end{Code}
19981998

19991999
(That was another \errmessage.)
20002000

‎ebook/leetcode.pdf‎

197 Bytes
Binary file not shown.

‎ebook/leetcode.synctex.gz‎

1.55 KB
Binary file not shown.

‎solution/src/main/java/com/inuker/solution/PalindromePermutationII.java‎

Lines changed: 32 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -7,30 +7,52 @@
77
* Created by dingjikerbo on 2016/12/19.
88
*/
99

10+
/**
11+
* https://leetcode.com/articles/palindrome-permutation-ii/
12+
*/
1013
public class PalindromePermutationII {
1114
/**
1215
* 这题就是生成一半的所有排列，然后镜像
1316
*/
14-
public List<String> generatePalindromes(String s) {
17+
public static List<String> generatePalindromes(String s) {
1518
int[] counts = new int[256];
1619
for (char c : s.toCharArray()) {
1720
counts[c]++;
1821
}
22+
List<String> list = new LinkedList<>();
1923
StringBuilder sb = new StringBuilder();
20-
StringBuilder single = new StringBuilder();
24+
char single = 0;
2125
for (int i = 0; i < counts.length; i++) {
22-
int count = counts[i];
23-
for ( ; count > 1; sb.append((char) i), count -= 2);
24-
if (count == 1) {
25-
single.append((char) i);
26+
if (counts[i] % 2 != 0) {
27+
if (single != 0) {
28+
return list;
29+
}
30+
single = (char) i;
31+
counts[i] = ((counts[i] >> 1) << 1);
32+
}
33+
for (int j = 0; j < counts[i]; j += 2) {
34+
sb.append((char)i);
2635
}
2736
}
28-
List<String> result = new LinkedList<String>();
29-
helper(sb.toString(), single.toString(), result);
30-
return result;
37+
38+
helper(sb, "" + (single != 0 ? single : ""), list);
39+
return list;
3140
}
3241

33-
private void helper(String s, String t, List<String> list) {
42+
private static void helper(StringBuilder sb, String cur, List<String> list) {
43+
if (sb.length() == 0) {
44+
list.add(cur);
45+
return;
46+
}
3447

48+
for (int i = 0; i < sb.length(); i++) {
49+
if (i > 0 && sb.charAt(i) == sb.charAt(i - 1)) {
50+
continue;
51+
}
52+
char c = sb.charAt(i);
53+
sb.deleteCharAt(i);
54+
helper(sb, c + cur + c, list);
55+
sb.insert(i, c);
56+
}
3557
}
3658
}

‎test/src/main/java/com/example/Main.java‎

Lines changed: 45 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
import java.util.Arrays;
1717
import java.util.HashMap;
1818
import java.util.Hashtable;
19+
import java.util.LinkedList;
1920
import java.util.List;
2021
import java.util.Map;
2122
import java.util.Objects;
@@ -26,9 +27,51 @@
2627
public class Main {
2728

2829
public static void main(String[] args) {
29-
List<String> list = new RestoreIPAddresses().restoreIpAddresses("010010");
30+
List<String> list = generatePalindromes("a");
3031
for (String s : list) {
31-
System.out.println(s);
32+
System.out.println("(" + s+")");
33+
}
34+
}
35+
36+
public static List<String> generatePalindromes(String s) {
37+
int[] counts = new int[256];
38+
for (char c : s.toCharArray()) {
39+
counts[c]++;
40+
}
41+
List<String> list = new LinkedList<>();
42+
StringBuilder sb = new StringBuilder();
43+
char single = 0;
44+
for (int i = 0; i < counts.length; i++) {
45+
if (counts[i] % 2 != 0) {
46+
if (single != 0) {
47+
return list;
48+
}
49+
single = (char) i;
50+
counts[i] = ((counts[i] >> 1) << 1);
51+
}
52+
for (int j = 0; j < counts[i]; j += 2) {
53+
sb.append((char)i);
54+
}
55+
}
56+
57+
helper(sb, "" + (single != 0 ? single : ""), list);
58+
return list;
59+
}
60+
61+
private static void helper(StringBuilder sb, String cur, List<String> list) {
62+
if (sb.length() == 0) {
63+
list.add(cur);
64+
return;
65+
}
66+
67+
for (int i = 0; i < sb.length(); i++) {
68+
if (i > 0 && sb.charAt(i) == sb.charAt(i - 1)) {
69+
continue;
70+
}
71+
char c = sb.charAt(i);
72+
sb.deleteCharAt(i);
73+
helper(sb, c + cur + c, list);
74+
sb.insert(i, c);
3275
}
3376
}
3477
}

0 commit comments

Comments
 (0)