当前位置：首页 > article >正文

LeetCode2506

article 2025/2/23 15:28:06

LeetCode2506

题目描述

给你一个字符串数组 words，数组中的每个字符串都具有相同的长度。

如果两个字符串包含的字符完全相同（忽略顺序和重复字符），则称这两个字符串是相似的。

请你返回 words 中相似字符串对的数量。

示例

示例 1

输入:

words = ["aba", "aabb", "abcd", "bac", "aabc"]

输出:

解释:

字符串 “aba” 和 “aabb” 是相似的，因为它们都包含字符 a 和 b。
字符串 “abcd” 和 “bac” 是相似的，因为它们都包含字符 a、b 和 c。
其他字符串对不相似，因此相似字符串对的数量为 2。

示例 2

输入:

words = ["aabb", "ab", "ba"]

输出:

解释:

字符串 “aabb” 和 “ab” 是相似的，因为它们都包含字符 a 和 b。
字符串 “aabb” 和 “ba” 是相似的，因为它们都包含字符 a 和 b。
字符串 “ab” 和 “ba” 是相似的，因为它们都包含字符 a 和 b。
因此，相似字符串对的数量为 3。

思路分析

问题核心

我们需要统计字符串数组中相似字符串对的数量。两个字符串相似的条件是它们包含的字符完全相同（忽略顺序和重复字符）。

思路拆解

字符集合表示：
- 使用一个整数（位掩码）表示一个字符串的字符集合。例如，字符 a 对应第 0 位，字符 b 对应第 1 位，依此类推。
哈希表统计：
- 使用哈希表 map 统计每个字符集合出现的次数。
相似对计算：
- 对于每个字符串，计算其字符集合的位掩码。
- 如果该位掩码已经在哈希表中出现过，则累加对应的次数到结果中。
- 更新哈希表中该位掩码的出现次数。

代码段

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

在这里插入图片描述

代码逐行讲解

1. 初始化哈希表

HashMap<Integer, Integer> map = new HashMap<>();

map 用于统计每个字符集合（位掩码）出现的次数。

2. 初始化结果

int ans = 0;

ans 用于存储相似字符串对的数量。

3. 遍历字符串数组

for (String word : words) {

遍历数组中的每个字符串。

4. 初始化位掩码

int index = 0;

index 用于表示当前字符串的字符集合的位掩码。

5. 计算字符集合的位掩码

for (char c : word.toCharArray()) {
    index |= 1 << (c - 'a');
}

遍历字符串中的每个字符，将其对应的位设置为 1。
c - 'a' 计算字符 c 对应的位索引（a 对应 0，b 对应 1，依此类推）。
1 << (c - 'a') 将 1 左移对应的位数。
index |= ... 将对应位设置为 1。

6. 累加相似对数量

ans += map.getOrDefault(index, 0);

如果当前字符集合的位掩码已经在哈希表中出现过，则累加对应的次数到结果中。

7. 更新哈希表

map.put(index, map.getOrDefault(index, 0) + 1);

更新哈希表中当前字符集合的位掩码的出现次数。

8. 返回结果

return ans;

返回相似字符串对的数量。

复杂度分析

时间复杂度

遍历字符串数组的时间复杂度为 O(n)，其中 n 是数组的长度。
对于每个字符串，遍历其字符的时间复杂度为 O(m)，其中 m 是字符串的长度。
因此，总时间复杂度为 O(n * m)。

空间复杂度

哈希表 map 的空间复杂度为 O(n)，其中 n 是数组的长度。

总结的知识点

1. 位掩码

使用位掩码表示字符集合，方便快速计算和比较。

实际例子

假设处理单词"bad"：

对于’b’ (c = ‘b’)，index |= 1 << 1，index变成0…010。
对于’a’ (c = ‘a’)，index |= 1 << 0，index变成0…011。
对于’d’ (c = ‘d’)，index |= 1 << 3，最终index变成0…1011。

2. 哈希表

使用哈希表统计字符集合的出现次数。

3. 字符串遍历

遍历字符串中的每个字符，计算其对应的位掩码。

4. 相似对统计

通过哈希表快速统计相似字符串对的数量。

整合

class Solution {
    public int similarPairs(String[] words) {
        HashMap<Integer, Integer> map = new HashMap<>(); // 哈希表统计字符集合
        int ans = 0; // 结果
        for (String word : words) {
            int index = 0; // 字符集合的位掩码
            for (char c : word.toCharArray()) {
                index |= 1 << (c - 'a'); // 更新位掩码
            }
            ans += map.getOrDefault(index, 0); // 累加相似对数量
            map.put(index, map.getOrDefault(index, 0) + 1); // 更新哈希表
        }
        return ans; // 返回结果
    }
}