[LeetCode] 2506. Count Pairs Of Similar Strings

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.

统计相似字符串对的数目。

给你一个下标从 0 开始的字符串数组 words 。

如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。

例如，”abca” 和 “cba” 相似，因为它们都由字符 ‘a’、’b’、’c’ 组成。
然而，”abacba” 和 “bcfd” 不相似，因为它们不是相同字符组成的。
请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= words.length - 1 。

思路

思路是类似 two sum 的做法。

暴力解的做法是把每两个不同的字符串拿出来作比较，如果他们构成题目定义的相似，则结果加一。这个做法肯定是O(n^2)的复杂度。

优化的思路需要考虑能否用空间换时间。这里我们用 hashmap 把每个字符串里的字符统计出来，然后用一个字符串的字符统计结果作为 key，然后遍历所有字符串，如果有相同的 key，则结果加一。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int similarPairs(String[] words) {
        HashMap<String, Integer> map = new HashMap<>();
        int res = 0;
        int n = words.length;
        for (int i = 0; i < n; i++) {
            String word = words[i];
            String key = helper(word);
            res += map.getOrDefault(key, 0);
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        return res;
    }

    private String helper(String word) {
        char[] map = new char[26];
        for (char c : word.toCharArray()) {
            if (map[c - 'a'] == 0) {
                map[c - 'a']++;
            }
        }
        return new String(map);
    }
}