Question

2506. Count Pairs Of Similar Strings

中文文档

Description

You are given a 0-indexed string array words.

Two strings are similar if they consist of the same characters.

• For example, "abca" and "cba" are similar since both consist of characters 'a', 'b', and 'c'.
• However, "abacba" and "bcfd" are not similar since they do not consist of the same characters.

Return _the number of pairs _(i, j)_ such that _0 <= i < j <= word.length - 1_ and the two strings _words[i]_ and _words[j]_ are similar_.

 

Example 1:

Input: words = ["aba","aabb","abcd","bac","aabc"]
Output: 2
Explanation: There are 2 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. 
- i = 3 and j = 4 : both words[3] and words[4] only consist of characters 'a', 'b', and 'c'. 

Example 2:

Input: words = ["aabb","ab","ba"]
Output: 3
Explanation: There are 3 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. 
- i = 0 and j = 2 : both words[0] and words[2] only consist of characters 'a' and 'b'.
- i = 1 and j = 2 : both words[1] and words[2] only consist of characters 'a' and 'b'.

Example 3:

Input: words = ["nba","cba","dba"]
Output: 0
Explanation: Since there does not exist any pair that satisfies the conditions, we return 0.

 

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consist of only lowercase English letters.

Solutions

Solution 1

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

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;
  }
}

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;
  }
};

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
}

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;
}

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
  }
}