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 <= 100

  • 1 <= words[i].length <= 100

  • words[i] 仅由小写英文字母组成

思路

一、统计字母出现的个数，使用int来计算对应数字 3ms

  1. 使用boolean数组记录字母是否使用

  2. 通过boolean数组来生成对应int数字(32位)

  3. 两两比较看是否成对，统计对数

二、统计字母出现的个数，使用int来计算对应数字(优化) 3ms

  1. 使用或位运算替换boolean数组记录降低空间复杂度

  2. 两两比较看是否成对，统计对数

三、统计字母出现的个数，使用int来计算对应数字(优化双重for循环) 1ms

  1. 使用或位运算替换boolean数组记录降低时间复杂度

  2. 抽取双重遍历for循环，内循环单独一个方法

  3. 两两比较看是否成对，统计对数

代码

一、统计字母出现的个数，使用int来计算对应数字

class Solution {
    public int similarPairs(String[] words) {
        int result = 0;
        int[] counts = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            boolean[] flags = new boolean[26];
            for (int j = 0; j < words[i].length(); j++) {
                flags[words[i].charAt(j) - 'a'] = true;
            }
            int temp = 0;
            for (boolean flag : flags) {
                if (flag) {
                    temp++;
                }
                temp <<= 1;
            }
            counts[i] = temp;
        }
        for (int i = 0; i < counts.length; i++) {
            for (int j = i + 1; j < counts.length; j++) {
                if (counts[i] == counts[j]) {
                    result++;
                }
            }
        }
        return result;
    }
}

二、统计字母出现的个数，使用int来计算对应数字(优化)

class Solution {
    public int similarPairs(String[] words) {
        int result = 0;
        int[] counts = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                counts[i] = counts[i] | (1 << words[i].charAt(j) - 'a');
            }
        }
        for (int i = 0; i < counts.length; i++) {
            for (int j = i + 1; j < counts.length; j++) {
                if (counts[i] == counts[j]) {
                    result++;
                }
            }
        }
        return result;
    }
}

三、统计字母出现的个数，使用int来计算对应数字(优化双重for循环)

class Solution {
    public int similarPairs(String[] words) {
        int result = 0;
        int[] counts = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            counts[i] = wordBit(words[i]);
        }
        for (int i = 0; i < counts.length; i++) {
            for (int j = i + 1; j < counts.length; j++) {
                if (counts[i] == counts[j]) {
                    result++;
                }
            }
        }
        return result;
    }

    private int wordBit(String word) {
        int len = word.length();
        int bit = 0;
        for (int i = 0; i < len; i++) {
            bit |= 1 << (word.charAt(i) - 'a');
        }
        return bit;
    }
}