Easy

题目描述

给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。

如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配：

  • 字符串 words[i] 等于 words[j] 的反转字符串。
  • 0 <= i < j < words.length

请你返回数组 words 中的 最大 匹配数目。

注意，每个字符串最多只能属于一对匹配。

示例 1：

输入：words = ["cd","ac","dc","ca","zz"]
输出：2
解释：在此示例中，我们可以通过以下方式匹配 2 对字符串：
- 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 "dc" 并且等于 words[2]。
- 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 "ca" 并且等于 words[3]。
可以证明最多匹配数目是 2 。

示例 2：

输入：words = ["ab","ba","cc"]
输出：1
解释：在此示例中，我们可以通过以下方式匹配 1 对字符串：
- 我们将第 0 个字符串与第 1 个字符串匹配，因为 words[1] 的反转字符串是 "ab" 并且等于 words[0] 。
可以证明最多匹配数目是 1 。

示例 3：

输入：words = ["aa","ab"]
输出：0
解释：在此示例中，无法匹配任何字符串。

提示：

  • 1 <= words.length <= 50
  • words[i].length == 2
  • words 包含互不相同的字符串
  • words[i] 仅包含小写英文字母

解题思路

解题思路

这道题要求找出最大的字符串配对数目，其中每对字符串互为反转关系。

方法一：哈希表统计（推荐）

由于字符串长度固定为2，我们可以使用哈希表来统计每个字符串的出现次数。对于每个字符串，我们检查它的反转字符串是否已经在哈希表中出现过：

  • 如果出现过，说明找到了一对，配对数加1，并将反转字符串的计数减1
  • 如果没有出现过，将当前字符串加入哈希表

这种方法的优点是只需要遍历一次数组，时间复杂度为O(n)。

方法二：暴力枚举

遍历所有可能的字符串对(i,j)，其中i < j，检查words[i]是否等于words[j]的反转字符串。使用一个布尔数组标记已经配对的字符串，避免重复配对。

由于题目保证所有字符串互不相同且长度为2，方法一更加高效简洁。

代码实现

class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        unordered_map<string, int> count;
        int pairs = 0;
        
        for (const string& word : words) {
            string reversed = word;
            reverse(reversed.begin(), reversed.end());
            
            if (count[reversed] > 0) {
                pairs++;
                count[reversed]--;
            } else {
                count[word]++;
            }
        }
        
        return pairs;
    }
};

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        count = {}
        pairs = 0
        
        for word in words:
            reversed_word = word[::-1]
            
            if count.get(reversed_word, 0) > 0:
                pairs += 1
                count[reversed_word] -= 1
            else:
                count[word] = count.get(word, 0) + 1
        
        return pairs

public class Solution {
    public int MaximumNumberOfStringPairs(string[] words) {
        Dictionary<string, int> count = new Dictionary<string, int>();
        int pairs = 0;
        
        foreach (string word in words) {
            char[] chars = word.ToCharArray();
            Array.Reverse(chars);
            string reversed = new string(chars);
            
            if (count.ContainsKey(reversed) && count[reversed] > 0) {
                pairs++;
                count[reversed]--;
            } else {
                if (count.ContainsKey(word)) {
                    count[word]++;
                } else {
                    count[word] = 1;
                }
            }
        }
        
        return pairs;
    }
}

var maximumNumberOfStringPairs = function(words) {
    const count = new Map();
    let pairs = 0;
    
    for (const word of words) {
        const reversed = word.split('').reverse().join('');
        
        if (count.get(reversed) > 0) {
            pairs++;
            count.set(reversed, count.get(reversed) - 1);
        } else {
            count.set(word, (count.get(word) || 0) + 1);
        }
    }
    
    return pairs;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表方法暴力枚举方法
时间复杂度O(n)O(n²)
空间复杂度O(n)O(n)

其中 n 是数组 words 的长度。哈希表方法只需遍历一次数组，而暴力方法需要检查所有字符串对。

相关题目