统计相似字符串对的数目

难度: Easy

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

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

例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。
然而，"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。

请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= words.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 <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成

Submission

运行时间: 27 ms

内存: 16.4 MB

from typing import List
from collections import Counter

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        count = 0
        n = len(words)
        for i in range(n):
            for j in range(i + 1, n):
                if self.is_similar(words[i], words[j]):
                    count += 1
        return count

    def is_similar(self, word1: str, word2: str) -> bool:
        return Counter(word1) == Counter(word2)

from typing import List
from collections import Counter

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        counts = {}
        similar_pairs = 0

        for word in words:
            count = tuple(Counter(word).values())
            if count in counts:
                similar_pairs += counts[count]
                counts[count] += 1
            else:
                counts[count] = 1

        return similar_pairs

from typing import List

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        count = 0
        char_sets = {}  # Mapping from character set to its frequency.

        for word in words:
            char_set = frozenset(word)  # Creating a frozenset of characters to use as a dictionary key.
            if char_set in char_sets:
                count += char_sets[char_set]  # Adding the number of previous occurrences of this char set.
                char_sets[char_set] += 1  # Incrementing the frequency of this char set.
            else:
                char_sets[char_set] = 1  # Recording the first occurrence of this char set.

        return count

# Testing the solution
sol = Solution()
print(sol.similarPairs(["aba", "aabb", "abcd", "bac", "aabc"]))  # Output: 2
print(sol.similarPairs(["aabb", "ab", "ba"]))  # Output: 3
print(sol.similarPairs(["nba", "cba", "dba"]))  # Output: 0

Explain

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

时间复杂度: O(n * m)

空间复杂度: O(n)

from typing import List

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        count = 0  # 用于存储相似对的数量
        char_sets = {}  # Mapping from character set to its frequency.

        for word in words:
            char_set = frozenset(word)  # Creating a frozenset of characters to use as a dictionary key.
            if char_set in char_sets:
                count += char_sets[char_set]  # Adding the number of previous occurrences of this char set.
                char_sets[char_set] += 1  # Incrementing the frequency of this char set.
            else:
                char_sets[char_set] = 1  # Recording the first occurrence of this char set.

        return count  # 返回计算出的相似对数量

# Testing the solution
sol = Solution()
print(sol.similarPairs(['aba', 'aabb', 'abcd', 'bac', 'aabc']))  # Output: 2
print(sol.similarPairs(['aabb', 'ab', 'ba']))  # Output: 3
print(sol.similarPairs(['nba', 'cba', 'dba']))  # Output: 0

Explore

在计算字符串相似对时选择使用 `frozenset` 主要是因为 `frozenset` 是不可变的，可以作为字典的键。此外，`frozenset` 自动处理了字符的去重和排序问题，确保只要组成字符相同，无论字符顺序如何，都映射到相同的键。而列表或元组虽然可以保存字符，但它们保存的是字符的顺序信息，不适合此类应用场景，因为相似字符串的定义仅与字符种类和数量有关，与顺序无关。

题解中将字符完全相同但顺序不同的字符串视为相似的设计选择，是基于对相似字符串的定义——即两个字符串包含完全相同的字符集合。这种设计允许算法以高效的方式通过字符集合来识别和统计相似字符串对，避免了复杂的排序或多重循环比较，显著提高了算法效率。

如果输入数组 `words` 为空，根据题解的算法逻辑，字典 `char_sets` 也将保持为空状态。因为没有字符串进行处理，循环不会执行任何操作，相似对的计数 `count` 将保持初始值0。因此，算法会返回0，表明没有找到任何相似的字符串对。这种处理方式自然地解决了空输入数组的情况，无需额外的特殊处理代码。

题解算法在遇到重复的字符串时，会将这些字符串对应的字符集 `char_set` 的出现频率进行累加。每次遇到已存在的字符集时，算法会将该字符集的当前频率（即之前出现的次数）加到相似对计数 `count` 上，并将频率增加1。这意味着，如果数组中有多个相同的字符串，每一个后续出现的相同字符串都会与前面的所有相同字符串形成新的相似对，从而正确地统计总的相似对数量。