【LeetCode: 2506. 统计相似字符串对的数目 + 模拟 + 哈希表】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 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] 仅由小写英文字母组成

🌟 求解思路&实现代码&运行结果

⚡ 模拟 + 哈希表

🥦 求解思路

1. 核心思想：通过双重循环遍历字符串数组，比较每一对字符串的字符集合是否完全相同。

2. 关键点：

   • 使用 HashSet 存储每个字符串的字符集合，去重后比较。

   • 如果两个字符串的字符集合完全相同，则计数器加 1。

3. 适用场景：该解法适用于需要统计字符串数组中相似字符串对的问题，如“统计相似字符串对的数目”、“字符串集合比较”等。

4. 有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {
    public int similarPairs(String[] words) {
        int n = words.length;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            String s = words[i];
            HashSet<Character> set = new HashSet<>();
            for (char c : s.toCharArray()) {
                set.add(c);
            }
            for (int j = i + 1; j < n; j++) {
                String next = words[j];
                boolean flag = true;
                HashSet<Character> set1 = new HashSet<>();
                for (char c : next.toCharArray()) {
                    set1.add(c);
                    if (!set.contains(c)) {
                        flag = false;
                        break;
                    }
                }
                if (flag && set1.size() == set.size()) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

🥦 运行结果

💬 共勉