Easy

题目描述

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

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

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

请你找出满足 0 <= i < j <= words.length - 1 且第 i 个和第 j 个字符串相似的下标对 (i, j) 的数目。

示例 1：

输入：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' 组成。

示例 2：

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

示例 3：

输入：words = ["nba","cba","dba"]
输出：0
解释：不存在满足条件的对，返回 0。

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] 仅由小写英文字母组成

解题思路

这道题的核心在于判断两个字符串是否由相同的字符组成。我们可以用以下几种方法来解决：

方法一：哈希集合表示（推荐）

对于每个字符串，将其转换为字符集合，然后比较两个集合是否相等。由于只包含小写字母，我们可以用位掩码优化空间。

方法二：位掩码优化

将每个字符串转换为一个整数，其中第i位表示字符’a’+i是否存在。相同的字符集合会产生相同的位掩码，然后统计相同位掩码的数量即可。

方法三：字符串标准化

将每个字符串的所有不同字符按字典序排列，形成标准化字符串。相同字符集合的字符串会有相同的标准化形式。

位掩码方法最优雅且高效，因为它将字符集合压缩为一个整数，比较和存储都很快速。我们统计每种字符集合出现的次数，然后计算组合数即可。

代码实现

class Solution {
public:
    int similarPairs(vector<string>& words) {
        unordered_map<int, int> maskCount;
        
        // 为每个字符串计算位掩码
        for (const string& word : words) {
            int mask = 0;
            for (char c : word) {
                mask |= (1 << (c - 'a'));
            }
            maskCount[mask]++;
        }
        
        // 计算相似对的数量
        int count = 0;
        for (auto& [mask, freq] : maskCount) {
            count += freq * (freq - 1) / 2;
        }
        
        return count;
    }
};

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        mask_count = {}
        
        # 为每个字符串计算位掩码
        for word in words:
            mask = 0
            for c in word:
                mask |= (1 << (ord(c) - ord('a')))
            mask_count[mask] = mask_count.get(mask, 0) + 1
        
        # 计算相似对的数量
        count = 0
        for freq in mask_count.values():
            count += freq * (freq - 1) // 2
        
        return count

public class Solution {
    public int SimilarPairs(string[] words) {
        var maskCount = new Dictionary<int, int>();
        
        // 为每个字符串计算位掩码
        foreach (string word in words) {
            int mask = 0;
            foreach (char c in word) {
                mask |= (1 << (c - 'a'));
            }
            if (maskCount.ContainsKey(mask)) {
                maskCount[mask]++;
            } else {
                maskCount[mask] = 1;
            }
        }
        
        // 计算相似对的数量
        int count = 0;
        foreach (int freq in maskCount.Values) {
            count += freq * (freq - 1) / 2;
        }
        
        return count;
    }
}

var similarPairs = function(words) {
    const maskCount = new Map();
    
    // 为每个字符串计算位掩码
    for (const word of words) {
        let mask = 0;
        for (const c of word) {
            mask |= (1 << (c.charCodeAt(0) - 'a'.charCodeAt(0)));
        }
        maskCount.set(mask, (maskCount.get(mask) || 0) + 1);
    }
    
    // 计算相似对的数量
    let count = 0;
    for (const freq of maskCount.values()) {
        count += Math.floor(freq * (freq - 1) / 2);
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n × m)，其中 n 是字符串数组长度，m 是字符串平均长度
空间复杂度O(n)，哈希表最多存储 n 个不同的位掩码

相关题目