Re: [閒聊] 每日leetcode
2131. Longest Palindrome by Concatenating Two Letter Words
陣列每個成員是長度 2 chars, 像是 aa, ab, cd
找拿他們拚最長迴文子字串的長度如 abcdeedcba 長度是 10
思路：
先建 HashMap 找頻率
然後遍歷他們
找正向跟反轉的頻率如 ab 就去找 ba
找他們較小頻率的加上去
之後 *4 加進 res
記得兩者都要減掉用過的頻率
然後找第二輪
這次找重複的如 aa, bb, cc
頻率直接 /2 *4 加進 res
最後看重複的有沒有孤兒
有的話中間可以放一個 +2 進 res
Code:
use std::collections::HashMap;
impl Solution {
pub fn longest_palindrome(words: Vec<String>) -> i32 {
let mut freq = HashMap::new();
for word in words {
*freq.entry(word).or_insert(0) += 1;
}
let mut res = 0;
let mut center_used = false;
for (word, &count) in freq.clone().iter() {
let rev: String = word.chars().rev().collect();
if word < &rev && freq.contains_key(&rev) {
let pair_count = count.min(*freq.get(&rev).unwrap());
res += pair_count * 4;
*freq.get_mut(word).unwrap() -= pair_count;
*freq.get_mut(&rev).unwrap() -= pair_count;
}
}
for (word, &count) in freq.iter() {
let rev: String = word.chars().rev().collect();
if word == &rev {
res += (count / 2) * 4;
if count % 2 == 1 && !center_used {
res += 2;
center_used = true;
}
}
}
res
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748256794.A.AF2.html
※ 編輯: yam276 (114.32.48.170 臺灣), 05/26/2025 18:54:50
→
05/26 18:55,
6月前
, 1F
05/26 18:55, 1F
→
05/26 18:55,
6月前
, 2F
05/26 18:55, 2F
→
05/26 18:55,
6月前
, 3F
05/26 18:55, 3F
→
05/26 18:56,
6月前
, 4F
05/26 18:56, 4F
→
05/26 18:57,
6月前
, 5F
05/26 18:57, 5F
→
05/26 18:57,
6月前
, 6F
05/26 18:57, 6F
→
05/26 18:59,
6月前
, 7F
05/26 18:59, 7F
→
05/26 19:00,
6月前
, 8F
05/26 19:00, 8F
→
05/26 19:03,
6月前
, 9F
05/26 19:03, 9F
討論串 (同標題文章)
完整討論串 (本文為第 1435 之 1548 篇)：