微网站设计尺寸,免费制作微网站,购买wordpress模板,网站维护预算题目描述#xff1a;
给你一个下标从 0 开始的字符串数组 words 。
如果两个字符串由相同的字符组成#xff0c;则认为这两个字符串 相似 。
例如#xff0c;abca 和 cba 相似#xff0c;因为它们都由字符 a、b、c 组成。然而#xff0c;
给你一个下标从 0 开始的字符串数组 words 。
如果两个字符串由相同的字符组成则认为这两个字符串 相似 。
例如abca 和 cba 相似因为它们都由字符 a、b、c 组成。然而abacba 和 bcfd 不相似因为它们不是相同字符组成的。
请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) 并返回下标对的数目其中 0 i j words.length - 1 。
代码思路
目标理解 给定一个字符串数组 words目标是找出所有满足条件的字符串对 (i, j)其中 words[i] 和 words[j] 由相同的字符组成并且 0 i j words.length - 1。 主要思路 字符集排序对于每个字符串我们可以将其字符去重并排序形成一个“标准化”的字符串。这样做的目的是为了将字符组成相同的字符串映射到同一个标准化字符串上。哈希表计数使用一个哈希表字典来记录每个标准化字符串出现的次数。计算相似对对于哈希表中每个标准化字符串如果出现次数大于1那么这些字符串之间可以组成相似对。相似对的数量可以通过组合数学计算得出即从 v 个相同的字符串中可以选出 C(v, 2) v * (v - 1) / 2 对相似对。 代码实现步骤 初始化一个计数器 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
