【力扣】2506：统计相似字符串对的数目

【力扣算法】2506：统计相似字符串对的数目

题目：

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

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

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

请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= words.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] 仅由小写英文字母组成

方法一

参考代码

/*** @param {string[]} words* @return {number}*/
var similarPairs = function (words) {if (words.length <= 0) return falselet count= 0;for (let i = 0; i < words.length; i++) {const set1 = new Set(words[i]);for (let j = i + 1; j < words.length; j++) {const set2 = new Set(words[j]);if (isSameSet(set1, set2)) {count++;}}}return count;
};function isSameSet(set1, set2) {if (set1.size !== set2.size) {return false;}for (let value of set1) {if (!set2.has(value)) {return false;}}return true;
}

思路解析

similarPairs 函数：
- 初始化一个变量 count 用于记录相似字符串对的数量。
- 使用两层嵌套的 for 循环遍历 words 数组中的每一对字符串。外层循环控制 i，内层循环控制 j，且保证 j > i。
- 对于每一对字符串 words[i] 和 words[j]，分别创建它们字符的集合 set1 和 set2。
- 调用 isSameSet 函数判断这两个集合是否相同，如果相同则 count 加 1。
- 最后返回 count。
isSameSet 函数：
- 首先检查两个集合的大小是否相同，如果不同则直接返回 false。
- 遍历第一个集合中的每个元素，检查第二个集合中是否包含该元素，如果有任何元素不在第二个集合中，则返回 false。
- 如果所有检查都通过，则返回 true，表示两个集合相同。

new Set() 是用来创建 Set 对象的构造函数。你可以给它传入一个可迭代对象（像数组、字符串之类的），构造函数会遍历这个可迭代对象，将其中的每个元素添加到新创建的 Set 中。

const word = "abca";
const charSet = new Set(word);
console.log(charSet); 
//在上述示例中，字符串 "abca" 被传入 new Set() 构造函数，最终生成的 charSet 是 Set(3) {'a', 'b', 'c'}。可以看到，重复的字符 'a' 只保留了一个。

方法二（官方题解）

参考代码

var similarPairs = function(words) {let res = 0;const cnt = new Map();for (const word of words) {let state = 0;for (const c of word) {state |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));}res += cnt.get(state) || 0;cnt.set(state, (cnt.get(state) || 0) + 1);}return res;
};

思路解析

字符串仅由小写字母组成，因此一个字符串含有的字符集合，可以用一个26位的二进制数字表示状态。从低位到高位，如果这一位为1，则表示含有对应的小写字母。遍历words，并用一个哈希表cnt记录每个状态出现的次数，对于每个word，计算其对应的状态state，并将结果增加cnt[state]，表示当前字符串与之前遍历过的所有同状态的字符串都相似，然后将cnt[state]自增1。最后返回结果。

复杂度分析