Leetcode2506：统计相似字符串对的数目

题目描述：

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

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

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

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

代码思路：

1. 目标理解：
   • 给定一个字符串数组 words，目标是找出所有满足条件的字符串对 (i, j)，其中 words[i] 和 words[j] 由相同的字符组成，并且 0 <= i < j <= words.length - 1。
2. 主要思路：
   • 字符集排序：对于每个字符串，我们可以将其字符去重并排序，形成一个“标准化”的字符串。这样做的目的是为了将字符组成相同的字符串映射到同一个标准化字符串上。
   • 哈希表计数：使用一个哈希表（字典）来记录每个标准化字符串出现的次数。
   • 计算相似对：对于哈希表中每个标准化字符串，如果出现次数大于1，那么这些字符串之间可以组成相似对。相似对的数量可以通过组合数学计算得出，即从 v 个相同的字符串中可以选出 C(v, 2) = v * (v - 1) / 2 对相似对。
3. 代码实现步骤：
   • 初始化一个计数器 res 为0，用于记录相似对的总数。
   • 初始化一个哈希表 dic，用于记录每个标准化字符串的出现次数。
   • 遍历字符串数组 words：
     • 对于每个字符串 w，将其字符去重并排序，形成一个标准化字符串 t。
     • 如果 t 不在哈希表 dic 中，则将其加入哈希表并设置计数为1；如果已经在哈希表中，则将计数加1。
   • 遍历哈希表 dic：
     • 对于每个键值对 (k, v)，如果 v > 1，则计算并累加相似对的数量 v * (v - 1) / 2 到 res。
   • 返回相似对的总数 res。

 代码实现：

class Solution:def similarPairs(self, words: List[str]) -> int:res = 0dic = dict()for w in words:ref = sorted(list(set(w)))t = "".join(ref)if t not in dic:dic[t] = 1else:dic[t] += 1for k,v in dic.items():if v > 1:res += (v*(v-1))//2return res