日期: 2025 年 2 月 22 日

目标

给你一个下标从 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] 仅由小写英文字母组成

思路

找出字符串数组 words 中由相同字母组成的单词对数目。

将构成单词的字母组合使用掩码表示，统计掩码相同的单词个数 n，从中任选 2 个组合的方法有 n * (n - 1) / 2。也可以直接在循环中累加结果，每增加一个 mask 相同的单词，组合数增加 prevCnt，即与前面的单词一一组合。

代码

/**
 * @date 2025-02-22 12:06
 */
public class SimilarPairs2506 {

    public int similarPairs_v1(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (String word : words) {
            int mask = 0;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                int offset = word.charAt(i) - 'a';
                mask |= 1 << offset;
            }
            int prevCnt = map.getOrDefault(mask, 0);
            res += prevCnt;
            map.put(mask, prevCnt + 1);
        }
        return res;
    }

    public int similarPairs(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        for (String word : words) {
            int mask = 0;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                int offset = word.charAt(i) - 'a';
                mask |= 1 << offset;
            }
            map.merge(mask, 1, Integer::sum);
        }
        return map.values().stream().mapToInt(x -> x * (x - 1) / 2).sum();
    }

}

性能