2506. 统计相似字符串对的数目 给你一个下标从 0 开始的字符串数组 words 。

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

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

请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= word.length - 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’ 。

输入：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’ 组成。

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 仅由小写英文字母组成

Solutions

class Solution {
    public int similarPairs(String[] words) {
        int count = 0;
        int len = words.length;
        int [][]arr = new int[len][26];
        for (int i = 0; i < len; i++) {
            for(char a : words[i].toCharArray()){
                arr[i][a-'a'] = 1;
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if(Arrays.equals(arr[i],arr[j])){
                    count++;
                }
            }
        }
        return count;
    }
}

Ideas

• 1.哈希表 + 位运算(状态压缩)

  由于单词只由小写字母构成，所以可以把单词中字符是否出现的状态用int的低26位表示，不同单词经过位运算操作后得到相同的值， 那么就可以说明这两个单词由相同类型的字符组成。我们可以维护一个哈希表，key记录单词压缩后的int值， value记录单词个数。 答案要求的是满足条件的对数！所以应该把它们依次加起来，注意一定是先加入答案 再自增！ 比如某个状态的value为4 表示该字符组合的单词有4个 共有 3 + 2 + 1 + 0 = 6对！不会把4加入答案！