跳转至

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

解法

方法一：哈希表 + 位运算

对于每个字符串，我们可以将其转换为一个长度为 $26$ 的二进制数，其中第 $i$ 位为 $1$ 表示该字符串中包含第 $i$ 个字母。

如果两个字符串包含相同的字母，则它们的二进制数是相同的，因此，对于每个字符串，我们用哈希表统计其二进制数出现的次数，每一次累加到答案中，再将其二进制数出现的次数加 $1$。

时间复杂度 $O(L)$，空间复杂度 $O(n)$。其中 $L$ 是所有字符串的长度之和，而 $n$ 是字符串的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def similarPairs(self, words: List[str]) -> int:
        ans = 0
        cnt = Counter()
        for w in words:
            v = 0
            for c in w:
                v |= 1 << (ord(c) - ord("A"))
            ans += cnt[v]
            cnt[v] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int similarPairs(String[] words) {
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (var w : words) {
            int v = 0;
            for (int i = 0; i < w.length(); ++i) {
                v |= 1 << (w.charAt(i) - 'a');
            }
            ans += cnt.getOrDefault(v, 0);
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int similarPairs(vector<string>& words) {
        int ans = 0;
        unordered_map<int, int> cnt;
        for (auto& w : words) {
            int v = 0;
            for (auto& c : w) v |= 1 << c - 'a';
            ans += cnt[v];
            cnt[v]++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func similarPairs(words []string) (ans int) {
    cnt := map[int]int{}
    for _, w := range words {
        v := 0
        for _, c := range w {
            v |= 1 << (c - 'a')
        }
        ans += cnt[v]
        cnt[v]++
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function similarPairs(words: string[]): number {
    let ans = 0;
    const cnt: Map<number, number> = new Map();
    for (const w of words) {
        let v = 0;
        for (let i = 0; i < w.length; ++i) {
            v |= 1 << (w.charCodeAt(i) - 'a'.charCodeAt(0));
        }
        ans += cnt.get(v) || 0;
        cnt.set(v, (cnt.get(v) || 0) + 1);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
use std::collections::HashMap;

impl Solution {
    pub fn similar_pairs(words: Vec<String>) -> i32 {
        let mut ans = 0;
        let mut hash: HashMap<i32, i32> = HashMap::new();

        for w in words {
            let mut v = 0;

            for c in w.chars() {
                v |= 1 << ((c as u8) - b'a');
            }

            ans += hash.get(&v).unwrap_or(&0);
            *hash.entry(v).or_insert(0) += 1;
        }

        ans
    }
}

评论