题目链接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 是另一个可以得到的最长回文串。解题思路问题理解题目要求从给定的单词数组中构造最长的回文串。回文串的特点是正读反读相同因此单词的排列需要满足对称性。关键观察对称单词如aa、“bb”可以成对使用或者单独一个放在中间。非对称单词如ab、“ba”必须成对出现即ab和ba的数量必须相等才能配对使用。算法设计统计每个单词的出现次数。对于对称单词尽可能多地成对使用并记录是否存在奇数次的对称单词。对于非对称单词取ab和ba中较小的出现次数成对使用。最终回文串的长度由成对单词的对数和是否有一个对称单词可以放在中间决定。题解代码classSolution{publicintlongestPalindrome(String[]words){// 创建一个26x26的二维数组用于统计每个单词出现的次数// cnt[i][j]表示第一个字母是(ai)第二个字母是(aj)的单词出现的次数int[][]cntnewint[26][26];// 遍历所有单词统计每个单词出现的次数for(Stringw:words){cnt[w.charAt(0)-a][w.charAt(1)-a];}intans0;// 用于记录最终的回文串长度intodd0;// 标记是否存在出现奇数次的对称单词如aa// 遍历所有可能的字母组合for(inti0;i26;i){// 处理对称单词如aa、bb等intccnt[i][i];// 取最大的偶数次因为对称单词需要成对出现才能构成回文ansc-c%2;// 如果存在奇数次的对称单词可以将其中的一个放在回文串的正中间odd|c%2;// 处理非对称单词如ab、ba等for(intji1;j26;j){// 取ab和ba中较小的出现次数因为它们需要成对出现ansMath.min(cnt[i][j],cnt[j][i])*2;}}// 最终回文串长度 (成对单词的对数 * 2 是否有一个对称单词可以放在中间) * 2// 乘以2是因为每个单词长度为2return(ansodd)*2;}}复杂度分析时间复杂度统计单词出现次数O(n)其中n是单词数组的长度。遍历26x26的二维数组O(26^2) O(1)因为26是常数。总时间复杂度O(n 1) O(n)。空间复杂度使用了一个26x26的二维数组O(26^2) O(1)。其他变量是常数空间。总空间复杂度O(1)。