2506 统计相似字符串对的数目

地址：2506. 统计相似字符串对的数目 - 力扣（LeetCode）

题目描述

给你一个下标从 0 开始的字符串数组 words 。

如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。

• 例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。
• 然而，"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。

请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= words.length - 1 。

示例

1
2
3
4
5

输入：words = ["aba","aabb","abcd","bac","aabc"]
输出：2
解释：共有 2 对满足条件：
- i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。 
- i = 3 且 j = 4 ：words[3] 和 words[4] 只由字符 'a'、'b' 和 'c' 。 

思路

首先想到去重set比较

进一步想到哈希表

将字符串换位26位二进制数作哈希表下标，每个字符串都与之前判断过的哈希值相似

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int similarPairs(vector<string>& words) {
        unordered_map<int,int> cnt;
        int ans=0;
        for(auto &s :words){
            int mask=0;
            for(char c : s){
                mask|=1<<(c-'a');
            }
            ans+=cnt[mask]++;
        }
        return ans;
    }
};

• ← Previous Post
• Next Post →