LeetCode 题解工作台
最大字符串配对数目
给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。 如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配： 字符串 words[i] 等于 words[j] 的反转字符串。 0 请你返回数组 words 中的 最大 匹配数目。 注意，…
4
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用哈希表 来存储数组 中每个字符串的反转字符串出现的次数。 遍历数组 ，对于每个字符串 ，我们将其反转字符串 的出现次数加到答案中，然后将 的出现次数加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 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 <= 50words[i].length == 2words包含的字符串互不相同。words[i]只包含小写英文字母。
解题思路
方法一：哈希表
我们可以用哈希表 来存储数组 中每个字符串的反转字符串出现的次数。
遍历数组 ，对于每个字符串 ，我们将其反转字符串 的出现次数加到答案中，然后将 的出现次数加 。
最后返回答案。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def maximumNumberOfStringPairs(self, words: List[str]) -> int:
cnt = Counter()
ans = 0
for w in words:
ans += cnt[w[::-1]]
cnt[w] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for candidates who use a hash table for efficient lookups.
- question_mark
Evaluate if the candidate ensures no duplicate pairs are counted.
- question_mark
Assess the candidate’s understanding of leveraging hash tables to optimize array scanning.
常见陷阱
外企场景- error
Forgetting to reverse each word and check for its pair.
- error
Not using a hash table, resulting in slow lookups.
- error
Miscounting pairs when both words are part of the same pair, leading to duplication.
进阶变体
外企场景- arrow_right_alt
Extend the problem by increasing the length of the words.
- arrow_right_alt
Use a different data structure to store the words, such as a set.
- arrow_right_alt
Modify the problem by considering multi-character words.