回傳傳入字串可造出的最長回文字串長度。
題目
Longest Palindrome Easy
Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Letters are case sensitive, for example, “Aa” is not considered a palindrome here.
我的解法
想法
偶數數量的字能在回文字串兩邊各放一半
奇數數量的字僅能放一組在中間
流程
計算與儲存各字母數量
依照各字母是否為奇數來計算回文字串長度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int longestPalindrome(String s) {
HashMap<Character, Integer> hm = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char schar = s.charAt(i);
hm.put(schar, hm.getOrDefault(schar, 0) + 1);
}
int output = 0;
boolean hasOdd = false;
for (int value : hm.values()) {
if (value % 2 != 0) {
hasOdd = true;
output += (value - 1);
} else {
output += value;
}
}
return hasOdd ? output + 1 : output;
}
}
|
重點物件或方法
檢討
看其他人滿多精巧的寫法，我的要跑兩次迴圈實在是太弱了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int longestPalindrome(String s) {
if (s == null || s.length() == 0){
return 0;
}
HashSet<Character> hs = new HashSet<Character>();
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (hs.contains(s.charAt(i))) {
hs.remove(s.charAt(i));
count++;
} else {
hs.add(s.charAt(i));
}
}
if (!hs.isEmpty()){
return count * 2 + 1;
}
return count * 2;
}
}
|
參考資料
409. Longest Palindrome: Java Solution