题目描述#

给你一个下标从 0 开始的字符串数组 words。如果两个字符串由相同的字符组成，则认为这两个字符串相似。例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成；然而，"abacba" 和 "bcfd" 不相似。请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j)，并返回下标对的数目，其中 0 <= i < j <= words.length - 1。

思路#

将每个字符串出现过的字符集合用 26 位二进制掩码表示，掩码相同即字符集合相同。遍历数组时为当前掩码累加已出现的相同掩码次数，就能得到与当前字符串相似的历史字符串数量；随后将当前掩码计数加一。整个过程只需一次遍历和一个哈希表。

时间复杂度 O(n * L)，其中 L 为单词长度；空间复杂度 O(n)。

代码#

class Solution {
    public int similarPairs(String[] words) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (String s : words) {
            int mask = 0; // 记录当前字符串的字符集合
            for (char c : s.toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            int c = cnt.getOrDefault(mask, 0);
            ans += c;
            cnt.put(mask, c + 1);
        }
        return ans;
    }
}

知识边界#

位掩码#

位掩码（Bitmask） 将一个字符串中“出现过哪些字符”压缩成一个整数，从而快速判断两个字符串是否由相同的字符集组成。

使用int32位进行状态压缩，可以覆盖26个字母的覆盖范围

mask |= 1 << (c - 'a'); mask向左移动 c - 'a'位

代码思路参考0x3f