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 :])