Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2022-11-03 10:33:23
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
作者: Bill8x1229 (20分鐘了還是想不到)   2022-11-03 10:34:00
大師
作者: pandix (麵包屌)   2022-11-03 10:49:00
大師
作者: itoumashiro (佩可咪口愛的結晶)   2022-11-03 11:34:00
怎麼沒有龍

Links booklink

Contact Us: admin [ a t ] ucptt.com