Re: [閒聊] 每日LeetCode已回收
2131. Longest Palindrome by Concatenating Two Letter Words
龍大是個回文廚，常常發文教育大家回文的美妙之處。
請幫龍大找出 words 中能組成的最長回文字串長度。word 為長度為 2 的小寫字母字串。
如果找不出來的話，龍大可能會做出一些蠢事……
Example 1:
Input: words = ["lc","cl","gg"]
Output: 6
最長回文字串(之一) "lcggcl"
Example 2:
Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
最長回文字串(之一) "tylcclyt"
Example 3:
Input: words = ["cc","ll","xx"]
Output: 2
"cc", "ll", "xx"都是 words 能組成的最長回文字串
思路:
1.因為每個 word 長度都是 2，最後組成的字串一定是由 word 兩兩相對
而相反的 word 一定是放在首尾相對的位置，可以用 Counter 算出每個 word 出現次數
然後看他和他的相反字能配成幾對，長度就能加上對數*4
例如 count["ab"] = 3, count["ba"] = 2 就能配出 ababxxxxxxxxbaba
長度就能加上 min(count["ab"], count["ba"]) * 4 = 8
因為在 iterate word 的時候每種組合會算到兩次所以*4可以改成*2就好
2.如果兩個字母一樣就只能跟自己配，能配的對數是 count[word] / 2
長度是加上 4 * (count[word] // 2) 記得要整數除法
另外如果有一個多出來的可以放在中間，可以隨便用 flag 記一下
3.Python code:
class Solution:
def longestPalindrome(self, words: List[str]) -> int:
count = Counter(words)
res = 0
single = 0
for word in count:
if word[0] == word[1]:
res += (count[word] // 2) * 4
single = 2 if count[word]%2 else single
else:
res += min(count[word], count[word[::-1]]) * 2
return res + single
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667442028.A.AA7.html
推
11/03 10:40,
3年前
, 1F
11/03 10:40, 1F
推
11/03 11:31,
3年前
, 2F
11/03 11:31, 2F
討論串 (同標題文章)
完整討論串 (本文為第 82 之 719 篇)：