class Solution {
public:
int similarPairs(vector<string>& words) {
}
};
2506. 统计相似字符串对的数目
给你一个下标从 0 开始的字符串数组 words 。
如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。
"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= word.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 <= 1001 <= words[i].length <= 100words[i] 仅由小写英文字母组成原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2025-02-22 00:09:41
use std::collections::HashMap;
impl Solution {
pub fn similar_pairs(words: Vec<String>) -> i32 {
let mut cnt = HashMap::new();
let mut ans = 0;
for s in words {
let mut mask = 0;
for c in s.bytes() {
mask |= 1 << (c - b'a');
}
ans += *cnt.get(&mask).unwrap_or(&0);
*cnt.entry(mask).or_insert(0) += 1;
}
ans
}
}
javascript 解法, 执行用时: 8 ms, 内存消耗: 58.1 MB, 提交时间: 2025-02-22 00:09:29
/**
* @param {string[]} words
* @return {number}
*/
var similarPairs = function(words) {
const cnt = new Map();
let ans = 0;
for (const s of words) {
let mask = 0;
for (const c of s) {
mask |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
const c = cnt.get(mask) ?? 0
ans += c;
cnt.set(mask, c + 1);
}
return ans;
};
cpp 解法, 执行用时: 4 ms, 内存消耗: 16 MB, 提交时间: 2025-02-22 00:09:15
class Solution {
public:
int similarPairs(vector<string>& words) {
unordered_map<int, int> cnt;
int ans = 0;
for (auto& s : words) {
int mask = 0;
for (char c : s) {
mask |= 1 << (c - 'a');
}
ans += cnt[mask]++;
}
return ans;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 43.3 MB, 提交时间: 2025-02-22 00:09:02
class Solution {
public int similarPairs(String[] words) {
Map<Integer, Integer> cnt = new HashMap<>();
int ans = 0;
for (String s : words) {
int mask = 0;
for (char c : s.toCharArray()) {
mask |= 1 << (c - 'a');
}
int c = cnt.getOrDefault(mask, 0);
ans += c;
cnt.put(mask, c + 1);
}
return ans;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 4.1 MB, 提交时间: 2022-12-20 09:16:31
func similarPairs(words []string) (ans int) {
cnt := map[int]int{}
for _, s := range words {
mask := 0
for _, c := range s {
mask |= 1 << (c - 'a')
}
ans += cnt[mask]
cnt[mask]++
}
return
}
python3 解法, 执行用时: 72 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-20 09:15:30
class Solution:
def similarPairs(self, words: List[str]) -> int:
ans, cnt = 0, Counter()
for s in words:
mask = 0
for c in s:
mask |= 1 << (ord(c) - ord('a'))
ans += cnt[mask]
cnt[mask] += 1
return ans