【Leetcode 每日一题】2506. 统计相似字符串对的数目

问题背景

给你一个下标从 $0$ 开始的字符串数组 $words$。
如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。

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

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

数据约束

• $1\le words.length\le 100$
• $1\le words[i].length\le 100$
• $words[i]$ 仅由小写英文字母组成

解题过程

想到了字符串映射和字符串哈希，没想到用位运算来进行压缩存储。统计数量的做法，参考 好数对数目 就可以了。

具体实现

class Solution {public int similarPairs(String[] words) {Map<Integer, Integer> count = new HashMap<>();int res = 0;for (String word : words) {int mask = 0;for (char c : word.toCharArray()) {mask |= 1 << (c - 'a');}int cur = count.getOrDefault(mask, 0);res += cur;count.put(mask, cur + 1);}return res;}
}