文章

[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,得到一个整数。这使得每个字符串都能通过一个整数来唯一表示其字符构成。

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

如果直接两两比较字符串,那么时间复杂度就是 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),使得算法在大规模数据下也能高效运行

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

License:  CC BY 4.0