Medium

题目描述

给你一个字符串数组 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" 是另一个可以创建的最长回文串。

示例 3：

输入：words = ["cc","ll","xx"]
输出：2
解释：一个最长的回文串是 "cc"，长度为 2。
注意，"ll" 是另一个可以创建的最长回文串，"xx" 也是。

提示：

  • 1 <= words.length <= 10^5
  • words[i].length == 2
  • words[i] 由小写英文字母组成

解题思路

这道题的核心思想是理解回文串的构造规律。对于两字母的单词，我们需要分两种情况考虑：

1. 对称单词（如 “aa”, “bb”）：

  • 这些单词可以成对使用，每对贡献4个字符长度
  • 如果有剩余的一个，可以放在回文串中心，贡献2个字符长度

2. 互为反转的单词对（如 “ab” 和 “ba”）：

  • 每对这样的单词可以分别放在回文串的两端，每对贡献4个字符长度

算法步骤：

  1. 使用哈希表统计每个单词的出现次数
  2. 遍历哈希表，对于每个单词：
    • 如果是对称单词（word[0] == word[1]），计算能组成的对数，并记录是否有剩余
    • 如果不是对称单词，寻找其反转单词，计算能组成的对数
  3. 最后加上一个对称单词（如果存在剩余）作为中心

这种贪心策略能够保证得到最长的回文串，因为我们尽可能多地使用了所有可能的单词对。

时间复杂度： O(n)，其中 n 是 words 的长度 空间复杂度： O(n)，用于存储哈希表

代码实现

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        unordered_map<string, int> count;
        for (const string& word : words) {
            count[word]++;
        }
        
        int result = 0;
        bool hasCenter = false;
        
        for (auto& [word, freq] : count) {
            if (word[0] == word[1]) {
                // 对称单词
                result += (freq / 2) * 4;
                if (freq % 2 == 1) {
                    hasCenter = true;
                }
            } else {
                // 非对称单词，寻找反转单词
                string reversed = string(1, word[1]) + string(1, word[0]);
                if (count.count(reversed) && word < reversed) {
                    result += min(freq, count[reversed]) * 4;
                }
            }
        }
        
        if (hasCenter) {
            result += 2;
        }
        
        return result;
    }
};

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        count = {}
        for word in words:
            count[word] = count.get(word, 0) + 1
        
        result = 0
        has_center = False
        
        for word, freq in count.items():
            if word[0] == word[1]:
                # 对称单词
                result += (freq // 2) * 4
                if freq % 2 == 1:
                    has_center = True
            else:
                # 非对称单词，寻找反转单词
                reversed_word = word[1] + word[0]
                if reversed_word in count and word < reversed_word:
                    result += min(freq, count[reversed_word]) * 4
        
        if has_center:
            result += 2
            
        return result

public class Solution {
    public int LongestPalindrome(string[] words) {
        Dictionary<string, int> count = new Dictionary<string, int>();
        foreach (string word in words) {
            if (count.ContainsKey(word)) {
                count[word]++;
            } else {
                count[word] = 1;
            }
        }
        
        int result = 0;
        bool hasCenter = false;
        
        foreach (var kvp in count) {
            string word = kvp.Key;
            int freq = kvp.Value;
            
            if (word[0] == word[1]) {
                // 对称单词
                result += (freq / 2) * 4;
                if (freq % 2 == 1) {
                    hasCenter = true;
                }
            } else {
                // 非对称单词，寻找反转单词
                string reversed = "" + word[1] + word[0];
                if (count.ContainsKey(reversed) && string.Compare(word, reversed) < 0) {
                    result += Math.Min(freq, count[reversed]) * 4;
                }
            }
        }
        
        if (hasCenter) {
            result += 2;
        }
        
        return result;
    }
}

/**
 * @param {string[]} words
 * @return {number}
 */
var longestPalindrome = function(words) {
    const count = new Map();
    for (const word of words) {
        count.set(word, (count.get(word) || 0) + 1);
    }
    
    let result = 0;
    let hasCenter = false;
    
    for (const [word, freq] of count) {
        if (word[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历所有单词统计频次，然后遍历哈希表处理
空间复杂度O(n)哈希表存储单词及其频次

相关题目