题目链接
分析
对于每一个字符串，使用一个数组来存储字符串中出现的字母，这个数组可以压缩成一个二进制数 $mask$
使用一个哈希表统计每个 $mask$ 出现的次数，遍历求和即可
代码实现
class Solution {
public:
int similarPairs(vector<string>& words) {
unordered_map<int, int> um;
int ans = 0;
for(string s : words) {
int mask = 0;
for(char c : s)
mask |= 1 << (c - 'a');
ans += um[mask]++;
}
return ans;
}
};
复杂度分析
- 时间复杂度：$O(C)$，$C$ 为 $words$ 中字符串长度之和
- 空间复杂度：$O(n)$
