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

LeetCode 2506.统计相似字符串对的数目：哈希表+位运算

article 2025/2/23 16:59:34

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

解题方法：哈希表+位运算

这道题不考虑每个字符的出现次数，只考虑是否出现过。一共26个字母，因此可以使用一个整数二进制下的低26位分别代表每个字母是否出现过（可以将之称为状态码）。

使用一个哈希表统计每种状态码的出现次数。遍历字符串数组，对于一个字符串，计算出它的状态码后：

先累加这种状态码的出现次数到答案中
更新哈希表中这种状态码的出现次数+1

即可。

时间复杂度 $O (N)$ ，其中 $N$ 是总字符数。
空间复杂度 $O (l e n (w or d s))$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-02-22 11:13:07
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-02-22 11:15:31
 */
class Solution {
private:
    inline int code(string& s) {
        int ans = 0;
        for (char c : s) {
            ans |= 1 << (c - 'a');
        }
        return ans;
    }
public:
    int similarPairs(vector<string>& words) {
        unordered_map<int, int> ma;
        int ans = 0;
        for (string& s : words) {
            int c = code(s);
            ans += ma[c];
            ma[c]++;
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-02-22 11:16:23
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-22 11:19:02
'''
from typing import List
from collections import defaultdict

class Solution:
    def code(self, word: str) -> int:
        ans = 0
        for c in word:
            ans |= 1 << (ord(c) - 97)
        return ans
    
    def similarPairs(self, words: List[str]) -> int:
        ans = 0
        ma = defaultdict(int)
        for s in words:
            c = self.code(s)
            ans += ma[c]
            ma[c] += 1
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-02-22 11:16:28
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-02-22 11:23:31
 */
import java.util.Map;
import java.util.HashMap;

class Solution {
    private int code(String s) {
        int ans = 0;
        for (char c : s.toCharArray()) {
            ans |= 1 << (c - 'a');
        }
        return ans;
    }

    public int similarPairs(String[] words) {
        Map<Integer, Integer> ma = new HashMap<>();
        int ans = 0;
        for (String s : words) {
            int c = code(s);
            ans += ma.getOrDefault(c, 0);
            ma.merge(c, 1, Integer::sum);
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-02-22 11:16:35
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-02-22 11:27:11
 */
package main


func code_CPOSS(s string) (ans int) {
    for _, c := range s {
        ans |= 1 << (c - 'a')
    }
    return
}

func similarPairs(words []string) (ans int) {
    ma := map[int]int{}
    for _, s := range words {
        c := code_CPOSS(s)
        ans += ma[c]
        ma[c]++
    }
    return
}