题目链接

2131. 连接两字母单词得到的最长回文串 - 力扣（LeetCode）

题目描述

给你一个字符串数组words。words中每个元素都是一个包含 两个 小写英文字母的单词。

请你从words中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。

请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回0。

回文串 指的是从前往后和从后往前读一样的字符串。

题目示例

示例 1 :

输入：words = ["lc","cl","gg"] 输出：6 解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。 "clgglc" 是另一个可以得到的最长回文串。

示例 2 :

输入：words = ["ab","ty","yt","lc","cl","ab"] 输出：8 解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。 "lcyttycl" 是另一个可以得到的最长回文串。

解题思路

1. 问题理解：题目要求从给定的单词数组中构造最长的回文串。回文串的特点是正读反读相同，因此单词的排列需要满足对称性。
2. 关键观察：
   • 对称单词（如"aa"、“bb”）：可以成对使用，或者单独一个放在中间。
   • 非对称单词（如"ab"、“ba”）：必须成对出现，即"ab"和"ba"的数量必须相等才能配对使用。
3. 算法设计：
   • 统计每个单词的出现次数。
   • 对于对称单词，尽可能多地成对使用，并记录是否存在奇数次的对称单词。
   • 对于非对称单词，取"ab"和"ba"中较小的出现次数，成对使用。
   • 最终回文串的长度由成对单词的对数和是否有一个对称单词可以放在中间决定。

题解代码

classSolution{publicintlongestPalindrome(String[]words){// 创建一个26x26的二维数组，用于统计每个单词出现的次数// cnt[i][j]表示第一个字母是('a'+i)，第二个字母是('a'+j)的单词出现的次数int[][]cnt=newint[26][26];// 遍历所有单词，统计每个单词出现的次数for(Stringw:words){cnt[w.charAt(0)-'a'][w.charAt(1)-'a']++;}intans=0;// 用于记录最终的回文串长度intodd=0;// 标记是否存在出现奇数次的对称单词（如"aa"）// 遍历所有可能的字母组合for(inti=0;i<26;i++){// 处理对称单词（如"aa"、"bb"等）intc=cnt[i][i];// 取最大的偶数次，因为对称单词需要成对出现才能构成回文ans+=c-c%2;// 如果存在奇数次的对称单词，可以将其中的一个放在回文串的正中间odd|=c%2;// 处理非对称单词（如"ab"、"ba"等）for(intj=i+1;j<26;j++){// 取"ab"和"ba"中较小的出现次数，因为它们需要成对出现ans+=Math.min(cnt[i][j],cnt[j][i])*2;}}// 最终回文串长度 = (成对单词的对数 * 2 + 是否有一个对称单词可以放在中间) * 2// 乘以2是因为每个单词长度为2return(ans+odd)*2;}}

复杂度分析

1. 时间复杂度：
   • 统计单词出现次数：O(n)，其中n是单词数组的长度。
   • 遍历26x26的二维数组：O(26^2) = O(1)，因为26是常数。
   • 总时间复杂度：O(n + 1) = O(n)。
2. 空间复杂度：
   • 使用了一个26x26的二维数组：O(26^2) = O(1)。
   • 其他变量是常数空间。
   • 总空间复杂度：O(1)。