统计相似字符串对的数目

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.

/*
 * 思路：
 * 使用Java Stream来处理字符串数组。
 * 对于每个字符串，提取其字符集（使用Set存储字符）。
 * 通过比较两个字符串的字符集是否相同来判断它们是否相似。
 * 使用flatMap和filter来生成并过滤满足条件的下标对。
 */
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class SolutionStream {
    public long similarPairs(String[] words) {
        return IntStream.range(0, words.length)
            .flatMap(i -> IntStream.range(i + 1, words.length)
                .filter(j -> {
                    Set<Character> set1 = wordsToSet(words[i]);
                    Set<Character> set2 = wordsToSet(words[j]);
                    return set1.equals(set2);
                })
            ).count();
    }

    private Set<Character> wordsToSet(String word) {
        Set<Character> set = new HashSet<>();
        for (char c : word.toCharArray()) {
            set.add(c);
        }
        return set;
    }
}

题解使用了一个简单而有效的方法来统计相似字符串对的数量。它首先创建一个字典 `char_sets` 来存储每个字符串的字符集合作为键，和这些集合出现的次数作为值。对于数组 `words` 中的每个单词，算法会计算其字符的集合（使用 `frozenset` 以确保集合可以作为字典的键）。如果这个字符集合已经出现在字典中，那么就将字典中该集合的值（即之前这种集合出现的次数）加到总的相似对计数 `count` 上。这样，对于任何新出现的相同字符集合的字符串，我们都能立即知道它与之前多少个字符串是相似的，从而更新计数器。最后，算法返回计数器的值，即为相似字符串对的总数。这种方法巧妙地利用了集合的唯一性和字典的高效查找特性，避免了复杂的双重循环比较。

O(n * m)

O(n)