-
Notifications
You must be signed in to change notification settings - Fork 8
/
LongestPalindrome.java
96 lines (88 loc) · 2.7 KB
/
LongestPalindrome.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
92
93
94
95
96
package hashtable;
// Source : https://leetcode.com/problems/longest-palindrome/
// Id : 409
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date : 2019-09-24
// Topic : Hashtable
// Level : Easy
// Other :
// Tips :
// Result : 100.00% 100%
public class LongestPalindrome {
// 68.10% 2ms 100.00%
public int longestPalindrome(String s) {
int[] table = new int[52];
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'A';
if (index < 26)
table[index]++;
else
table[index - 6]++;
}
int count = 0;
boolean odd = false;
for (int i = 0; i < 52; i++) {
if ((table[i] & 1) == 0)
count += table[i];
else {
odd = true;
if (table[i] > 1)
count += table[i] - 1;
}
}
return odd ? count + 1 : count;
}
public int longestPalindromeImprove(String s) {
// public int longestPalindrome(String s) {
int count = 0;
boolean[] table = new boolean[52];
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'A';
if (index < 26) {
if (table[index]) {
count += 2;
table[index] = false;
} else
table[index] = true;
} else {
if (table[index - 6]) {
count += 2;
table[index - 6] = false;
} else
table[index - 6] = true;
}
}
for (int i = 0; i < 52; i++) {
if (table[i] == true)
return count + 1;
}
return count;
}
public int longestPalindromeImprove2(String s) {
// public int longestPalindrome(String s) {
int count = 0;
boolean[] table = new boolean[58];// A 65 z 122
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'A';
if (table[index]) {
count += 2;
table[index] = false;
} else
table[index] = true;
}
return s.length() > count ? count + 1 : count;
}
// 100.00% 1ms 100.00%
public int longestPalindromeBest(String s) {
// public int longestPalindrome(String s) {
int count = 0;
int[] table = new int[58];// A 65 z 122
for (int i = 0; i < s.length(); i++) {
table[s.charAt(i) - 'A']++;
}
for (int i = 0; i < 58; i++) {
count += (table[i] >> 1) << 1;
}
return s.length() > count ? count + 1 : count;
}
}