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

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

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

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

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

示例 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] 仅由小写英文字母组成

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

由于只有小写字母，可以用一个整数 mask 表示字符串中出现过的字母。

遍历 words 的同时，用一个哈希表 cnt 维护 mask 的出现次数。先把 cnt}[\textit{mask}] 加到答案中，然后把 mask 的出现次数加一。

[sol1-Python3]

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        ans, cnt = 0, Counter()
        for s in words:
            mask = 0
            for c in s:
                mask |= 1 << (ord(c) - ord('a'))
            ans += cnt[mask]
            cnt[mask] += 1
        return ans

[sol1-Go]

func similarPairs(words []string) (ans int) {
	cnt := map[int]int{}
	for _, s := range words {
		mask := 0
		for _, c := range s {
			mask |= 1 << (c - 'a')
		}
		ans += cnt[mask]
		cnt[mask]++
	}
	return
}

复杂度分析

• 时间复杂度：O(L)，其中 L 为 words 中所有字符串的长度之和。
• 空间复杂度：O(n)，其中 n 为 words 的长度。