原文链接: https://leetcode-cn.com/problems/similar-string-groups

英文原文

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}.  Notice that "tars" and "arts" are in the same group even though they are not similar.  Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

 

Example 1:

Input: strs = ["tars","rats","arts","star"]
Output: 2

Example 2:

Input: strs = ["omv","ovm"]
Output: 1

 

Constraints:

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] consists of lowercase letters only.
• All words in strs have the same length and are anagrams of each other.

中文题目

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

 

示例 1：

输入：strs = ["tars","rats","arts","star"]
输出：2

示例 2：

输入：strs = ["omv","ovm"]
输出：1

 

提示：

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] 只包含小写字母。
• strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

通过代码

高赞题解

各位题友大家好，今天是每日算法题公众号坚持日更的第 7 天。今天力扣上的每日一题是第 839 题「839. 相似字符串组」。

题目大意

如果交换字符串 X  中的两个不同位置的字母，使得它和字符串 Y  相等，那么称 X 和 Y  两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，对于 [“tars”, “rats”, “arts”, “star”] 这四个字符串而言：

• “tars” 和 “rats” 是相似的 (交换 0 与 2 的位置)； “rats” 和 “arts” 也是相似的。
• 但是 “star” 不与 [“tars”，”rats”，”arts”] 中的任意一个相似，因为无法通过交换 star 中的两个不同位置字母得到三者的任意一个。

总之，它们通过相似性形成了两个关联组：**{“tars”, “rats”, “arts”} 和 {“star”}。注意，“tars”** 和 “arts” 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs 。列表中的每个字符串都是 strs  中其它所有字符串的一个字母异位词。请问 strs  中有多少个 相似字符串组？

示例：

输入：strs = ["tars","rats","arts","star"]
输出：2
解释：如题目上文所解释，可以分为 {"tars", "rats", "arts"} 和 {"star"} 两个相似字符串组。

解题思路

今天的题目的中文题意比较模糊，我看了很久才明白 相似字符串组 的含义。即相似字符串组中的每个字符串都有另外至少一个字符串和它相似。比如对于 {“tars”, “rats”, “arts”} 这个相似字符串组而言，相似关系是 “tars” <=> “rats” <=> “arts” 。

两个字符串相似的含义是能够通过交换两个字符的位置，得到另外一个字符串。判断两个字符串相似的时间的复杂度是 O(N)，因为把所有位置遍历一次，统计两个字符串的对应位置有多少不等即可。

明白了题意之后，做法也就呼之欲出了：把每个字符串当做图中的一个节点，如果两个字符串相似，那么它们之间就有一条边。图中的每个连通区域是一个相似字符串组。问：图中有多少个不连通的区域？

很显然，图的连通性问题可以用「并查集」去做。然后套「并查集」的模板就可以了。

这也是我之前说的：“在明白题目考察什么之后，剩下的就是套模板”。

和今天题目非常类似的题目是「1579. 保证图可完全遍历」，我前几天的文章已经详细分析过了，两者都是考察图中有多少个连通区域，都是直接使用并查集模板。

代码

每个字符串都是一个节点，我们需要分析每两个节点之间是否相似，如果相似就添加一条边，使用并查集，看最终有多少个连通区域。

代码思路：

1. 两重 for 循环，实现对节点之间两两组合，判断两个节点是否相似；
2. 判断相似的方法是：两个字符串的对应位置中只有 0 个或者 2 个不同；
3. 如果两个字符串相似则使用并查集，将此两个节点之间连通上一条边；
4. 统计最终并查集中有多少个不同的连通区域，即为所求。

复杂度分析：

1. 时间复杂度：$O(N ^ 2 * M)$，其中 $N$ 是数组的长度，$M$ 是单个字符串的长度。忽略了并查集的时间复杂度。这样一算，计算量大概 $10 ^ 8$，已经到达了力扣的计算量上限，刚好这题能过了。

2. 空间复杂度：$O(N)$，并查集需要一个长度为 $N$ 的数组。

使用 Python2 写的代码如下。

[]
class Solution(object):
    def numSimilarGroups(self, strs):
        """
        :type strs: List[str]
        :rtype: int
        """
        N = len(strs)
        dsu = DSU(N)
        for i in range(N):
            for j in range(i + 1, N):
                if self.isSimilar(strs[i], strs[j]):
                    dsu.union(i, j)
        return dsu.regions()
            
    def isSimilar(self, str1, str2):
        count = 0
        for i in range(len(str1)):
            if str1[i] != str2[i]:
                count += 1
        return count == 2 or count == 0

class DSU:
    def __init__(self, N):
        self.par_ = range(N + 1)
        self.regions_ = N

    def find(self, x):
        if x != self.par_[x]:
            self.par_[x] = self.find(self.par_[x])
        return self.par_[x]
    
    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        self.par_[px] = py
        self.regions_ -= 1
    
    def regions(self):
        return self.regions_

刷题心得

今天的题目考察并查集，仍然是可以直接套模板。本周已经连续考察了多个并查集问题，相信大家已经掌握了模板。昨天有群友说，感谢每日一题连续这么多次都是并查集题目，他现在已经能够背下来模板了。这也是大家的算法成长过程。刷题一定要坚持呀！

力扣题目一般是单一考点，即每个题目只考察一个知识点。因此做每个题目时，有一半的工作量是在思考这个题目在考察什么，剩下的一半工作量就是在套模板。把题目抽象成具体考察点的能力需要我们经常练习，也是靠多刷题来获得，当然啦，多看看每日算法题的解题思路，也会对大家很有帮助的！

OK，这就是本次题解的全部内容了，如果你觉得我的题解对你有帮助的话，求赞、求关注、求转发、求在看。你的认可就是我前进的最大动力！我们明天再见！

统计信息

通过次数	提交次数	AC比率
19537	33999	57.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言