Re: [閒聊] 每日LeetCode已回收
2131. Longest Palindrome by Concatenating Two Letter Words
給予很多個長度為2的字串，求出將這些字串任意拼接後可得的最長迴文長度。
Exaple：
Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of
length 6.
Note that "clgglc" is another longest palindrome that can be created.
思路：
1.任意兩字串要組成迴文需要滿足 ab => ba 或 aa => aa 它們必須成雙成對
（兩邊數量都大於1，並且取較小的那邊）
2.其中較特別的是自己就是迴文的字串（例如：aa）只有一個的時候加入字串
中間可以使迴文變長(lccl中間加上gg => lcggcl)
3.所以我們就先把所有字串放進map並統計數量，對自己就是迴文的字串做特殊處理
如果自己就是迴文的字串統計完數量後還有剩餘時，我們用一個flag紀錄，並在
返回res前判斷是否有多出一個自己就是迴文的字串，若有則答案要再多加2。
4.這邊我判斷迴文是奇數的時候更新flag並且把當前的數量減一就不會重複加到多個
重複迴文字串，例如：(5個aa、7個bb)
JavaCode：
class Solution {
public int longestPalindrome(String[] words) {
int res = 0;
Map<String, Integer> map = new HashMap<>();
for(String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
boolean middle = false;
for(String key : map.keySet()) {
if(key.charAt(0) == key.charAt(1)) {
int cnt = map.get(key);
if((cnt & 1) == 1) {
middle = true;
cnt--;
}
res += cnt*2;
continue;
}
String reverseKey = getKReverse(key);
if(map.containsKey(reverseKey)) {
res += Math.min(map.get(key), map.get(reverseKey))*2;
}
}
return middle ? res + 2 : res;
}
private String getKReverse(String s) {
return new String(new char[]{s.charAt(1), s.charAt(0)});
}
}
芒果假面
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.26.112 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667442805.A.E23.html
推
11/03 10:34,
3年前
, 1F
11/03 10:34, 1F
推
11/03 10:49,
3年前
, 2F
11/03 10:49, 2F
推
11/03 11:34,
3年前
, 3F
11/03 11:34, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 83 之 719 篇)：