【力扣算法】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 <= 1001 <= words[i].length <= 100words[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。最后返回结果。
复杂度分析
- 时间复杂度：O(m×n)，其中n是数组words的长度，m是数组words中单个字符串的平均长度。
- 空间复杂度：O(n)。