[LeetCode] 每日一题 2131. 连接两字母单词得到的最长回文串（贪心 + 哈希）
题目描述
给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
回文串 指的是从前往后和从后往前读一样的字符串。
题目链接
示例输入
示例 1
输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。示例 2
输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。示例 3
输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。提示
1 <= words.length <= 10^5words[i].length == 2words[i]仅包含小写英文字母。
解题思路
这是一道典型的“构造类”回文题，但和以往遇到的不同，这题限定了每个字符串都是两个小写字母，因此我们面对的是一种更有规律但仍需谨慎处理的场景。
🔍 常见陷阱：不要只考虑一种回文构造形式！
在构造回文串的题目中，一个常被忽视的点是：回文串不仅仅是像“ab + ba”这种对称结构，它还可能包含“aa”、“cc”等本身对称的字符串，作为中轴或两侧拼接。
比如：
"ab" + "ba" = "abba"，是通过反向字符串构成
"aa"、"cc" 这类自对称的串，也可以自己构成回文的一部分，甚至放在中心成为“ABA”结构中的“B”
但本题中，每个单词长度为2，意味着不会出现 “ABA” 这种奇数长度结构，但“AA”这样的偶数对称结构仍然是关键。
🎯基于这个思路，我们可以按以下步骤进行贪心处理：
遍历
words，对每个word找出其反转字符串如果哈希表中存在这个反转串，说明能成一对，如 "ab" 与 "ba"，拼成 "abba"，长度加4
如果没有，就将该字符串加入哈希表中待配对
特殊处理的是像 "aa" 这种自对称串
如果匹配成功，它也能成对，拼在回文两端
如果暂时没有配对，我们将它的数量记录在一个变量
sameCount中
最后，如果还有未被使用的自对称字符串（
sameCount > 0），我们可以选择其中一个放在回文串的正中间，额外加2
✨ 贪心策略总结：优先配对所有可形成回文对的串，再从剩下的对称串中挑一个放中心，构造的就是最长可能的回文
代码实现
class Solution {
public int longestPalindrome(String[] words) {
int count = 0;
int sameCount = 0;
HashMap<String, Integer> map = new HashMap<>();
for (String word : words) {
String reverseStr = new StringBuilder(word).reverse().toString();
int cnt = map.getOrDefault(reverseStr, 0);
if (cnt > 0) {
if (reverseStr.equals(word)) {
sameCount--;
}
count += 4;
map.put(reverseStr, cnt - 1);
} else {
if (reverseStr.equals(word)) {
sameCount++;
}
map.put(word, map.getOrDefault(word, 0) + 1);
}
}
if (sameCount != 0) {
count += 2;
}
return count;
}
}复杂度分析
⏱️ 时间复杂度：
每个字符串只处理一次，哈希表插入、查找都是常数时间
🧠 空间复杂度：
最坏情况下哈希表可能存储所有未配对字符串
总结
这题的关键不只是用哈希快速找反转字符串，更重要的是理解不同类型回文结构的构成方式，并合理处理“自对称字符串”是否可以放在中间的特殊情况
我在做题时第一反应就是从“对称匹配”角度出发，但也马上意识到像 “aa” 这种回文串很容易被忽视，因此特别引入了 sameCount 来记录这些未被使用的中轴候选项。整体实现上，这是一种“先两端对称，再考虑中心” 的典型贪心策略🫠🫠
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。