[LeetCode] 每日一题 2506. 统计相似字符串对的数目

题目链接

https://leetcode.cn/problems/count-pairs-of-similar-strings

题目描述

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

解题思路

今天的题目可以分为两个子问题来思考：

1. 如何表示一个字符串的字符构成

由于题目要求找出由相同字符组成的字符串对，因此我们需要一种高效的方式来表示一个字符串的字符构成。最直观的方式是使用一个布尔数组，标记每个字符是否出现，但这样做空间复杂度会较高。

后来我想到，因为字符串中的字符范围是固定的（只有小写字母），我们可以通过二进制数字来表示字符的构成。具体地，每个字符可以映射到一个二进制位上，使用“左移运算”和“或运算”来改变某一位的状态。例如，如果一个字符串包含字符 'a'、'b' 和 'c'，我们可以将这三个字符对应的位置的二进制位设置为 1，得到一个整数。这使得每个字符串都能通过一个整数来唯一表示其字符构成。

2. 如何统计相同字符构成的字符串对

如果直接两两比较字符串，那么时间复杂度就是 O(n^2)，这在大数据量情况下无法接受。为了优化这个过程，我们可以使用哈希表来记录每个字符构成（即二进制表示）的出现次数。对于每个新字符串，我们将其字符构成转换为二进制表示，然后查询哈希表中是否已经有相同的二进制表示。如果有，说明之前存在与当前字符串相似的字符串对，将这些字符串对的数量加到答案中。每次处理完当前字符串后，我们将它的字符构成存入哈希表中，并更新该字符构成的计数。

代码实现

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

复杂度分析

• 时间复杂度：时间复杂度主要取决于两部分：首先是每个字符串的处理过程，我们将每个字符串的字符转换为二进制表示，处理时间是 O(m)，其中 m 是字符串的最大长度。然后是哈希表的操作，它的时间复杂度是 O(1)。因此，整个算法的时间复杂度是 O(n * m)，其中 n 是字符串的个数，m 是字符串的最大长度

• 空间复杂度：空间复杂度主要由哈希表决定，用于存储每个字符构成的出现次数。在最坏情况下，哈希表的大小与字符串的个数成正比，因此空间复杂度是 O(n)

总结

这道题的关键点在于如何高效表示字符串的字符组成。通过使用二进制数来表示字符的出现，我们可以快速地进行相似字符串的判断。而通过哈希表来记录每种字符组合的出现次数，我们避免了直接的 O(n^2) 两两比较，成功将复杂度降到了 O(n * m)，使得算法在大规模数据下也能高效运行

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。