-
Notifications
You must be signed in to change notification settings - Fork 299
/
Code04_PalindromeWays.java
91 lines (83 loc) · 2 KB
/
Code04_PalindromeWays.java
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package class20;
public class Code04_PalindromeWays {
public static int ways1(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] s = str.toCharArray();
char[] path = new char[s.length];
return process(str.toCharArray(), 0, path, 0);
}
public static int process(char[] s, int si, char[] path, int pi) {
if (si == s.length) {
return isP(path, pi) ? 1 : 0;
}
int ans = process(s, si + 1, path, pi);
path[pi] = s[si];
ans += process(s, si + 1, path, pi + 1);
return ans;
}
public static boolean isP(char[] path, int pi) {
if (pi == 0) {
return false;
}
int L = 0;
int R = pi - 1;
while (L < R) {
if (path[L++] != path[R--]) {
return false;
}
}
return true;
}
public static int ways2(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] s = str.toCharArray();
int n = s.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int i = 0; i < n - 1; i++) {
dp[i][i + 1] = s[i] == s[i + 1] ? 3 : 2;
}
for (int L = n - 3; L >= 0; L--) {
for (int R = L + 2; R < n; R++) {
dp[L][R] = dp[L + 1][R] + dp[L][R - 1] - dp[L + 1][R - 1];
if (s[L] == s[R]) {
dp[L][R] += dp[L + 1][R - 1] + 1;
}
}
}
return dp[0][n - 1];
}
public static String randomString(int len, int types) {
char[] str = new char[len];
for (int i = 0; i < str.length; i++) {
str[i] = (char) ('a' + (int) (Math.random() * types));
}
return String.valueOf(str);
}
public static void main(String[] args) {
int N = 10;
int types = 5;
int testTimes = 100000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
int len = (int) (Math.random() * N);
String str = randomString(len, types);
int ans1 = ways1(str);
int ans2 = ways2(str);
if (ans1 != ans2) {
System.out.println(str);
System.out.println(ans1);
System.out.println(ans2);
System.out.println("Oops!");
break;
}
}
System.out.println("测试结束");
}
}