[LeetCode] 每日一题 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]
仅由小写英文字母组成
解题思路
今天的题目可以分为两个子问题来思考:
如何表示一个字符串的字符构成
由于题目要求找出由相同字符组成的字符串对,因此我们需要一种高效的方式来表示一个字符串的字符构成。最直观的方式是使用一个布尔数组,标记每个字符是否出现,但这样做空间复杂度会较高。
后来我想到,因为字符串中的字符范围是固定的(只有小写字母),我们可以通过二进制数字来表示字符的构成。具体地,每个字符可以映射到一个二进制位上,使用“左移运算”和“或运算”来改变某一位的状态。例如,如果一个字符串包含字符 'a'、'b' 和 'c',我们可以将这三个字符对应的位置的二进制位设置为 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),使得算法在大规模数据下也能高效运行
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。