Skip to content

2506. Count Pairs Of Similar Strings 👍

Approach 1: Brute Force

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int similarPairs(vector<string>& words) {
    int ans = 0;
    vector<int> masks;

    for (const string& word : words)
      masks.push_back(getMask(word));

    for (int i = 0; i < masks.size(); ++i)
      for (int j = i + 1; j < masks.size(); ++j)
        if (masks[i] == masks[j])
          ++ans;

    return ans;
  }

 private:
  int getMask(const string& word) {
    int mask = 0;
    for (const char c : word)
      mask |= 1 << c - 'a';
    return mask;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int similarPairs(String[] words) {
    int ans = 0;
    int[] masks = new int[words.length];

    for (int i = 0; i < words.length; ++i)
      masks[i] = getMask(words[i]);

    for (int i = 0; i < masks.length; ++i)
      for (int j = i + 1; j < masks.length; ++j)
        if (masks[i] == masks[j])
          ++ans;

    return ans;
  }

  private int getMask(final String word) {
    int mask = 0;
    for (const char c : word.toCharArray())
      mask |= 1 << c - 'a';
    return mask;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def similarPairs(self, words: List[str]) -> int:
    ans = 0

    def getMask(word: str) -> int:
      mask = 0
      for c in word:
        mask |= 1 << ord(c) - ord('a')
      return mask

    masks = [getMask(word) for word in words]

    for i in range(len(masks)):
      for j in range(i + 1, len(masks)):
        if masks[i] == masks[j]:
          ans += 1

    return ans

Approach 2: One-Liner

  • Time: $O(n^2)$
  • Space: $O(n)$
1
2
3
4
5
class Solution:
  def similarPairs(self, words: List[str]) -> int:
    return sum(set(words[i]) == set(words[j])
               for i in range(len(words))
               for j in range(i + 1, len(words)))