本文主要是介绍LeetCode 2744. 最大字符串配对数目,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目
1、题目描述
给你一个下标从 0 开始的数组
words
,数组中包含 互不相同 的字符串。如果字符串
words[i]
与字符串words[j]
满足以下条件,我们称它们可以匹配:
- 字符串
words[i]
等于words[j]
的反转字符串。0 <= i < j < words.length
请你返回数组
words
中的 最大 匹配数目。注意,每个字符串最多匹配一次。
2、接口描述
class Solution {
public:int maximumNumberOfStringPairs(vector<string>& words) {}
};
3、原题链接
2744. 最大字符串配对数目
二、解题报告
1、思路分析
小写字母ASCII值最大也就一百多,所以任意一个长度为2的小写字母串给它映射到整数上存起来,一次遍历即可。
2、复杂度
时间复杂度:O(N) 空间复杂度:O(N)
3、代码详解
C++
class Solution {
public:int maximumNumberOfStringPairs(vector<string>& words) {int ret = 0;unordered_set<int> hash;for(auto& x : words)hash.count(x[1] * 150 + x[0]) ? ++ret : (hash.insert(x[0] * 150 + x[1]) , 0);return ret; }
};
Python3
class Solution:def maximumNumberOfStringPairs(self, words: List[str]) -> int:return sum(1 for i , s in enumerate(words) if s[::-1] in words[i + 1 :])
这篇关于LeetCode 2744. 最大字符串配对数目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!