Skip to content

Latest commit

 

History

History
155 lines (105 loc) · 5.45 KB

839.similar-string-groups.md

File metadata and controls

155 lines (105 loc) · 5.45 KB
Raw

题目地址(839. 相似字符串组)

https://leetcode-cn.com/problems/similar-string-groups/

题目描述

如果交换字符串 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 <= 100
1 <= strs[i].length <= 1000
sum(strs[i].length) <= 2 * 10^4
strs[i] 只包含小写字母。
strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

 

备注：

      字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

前置知识

公司

  • 暂无

思路

将字符串看成图中的点，字符串的相似关系看成边， 即如果两个字符串 s1, s2 相似就在两个字符串之间添加一条无向边(s1, s2)。

相似关系其实是没有联通性的。比如 s1 和 s2 相似，s2 和 s3 相似，那么 s1 和 s3 不一定相似，但是 s1 ，s2，s3 应该在一个相似字符串数组中。而题目仅要求我们返回相似字符串数组的个数。 而在同一个相似字符串数组中的字符串却具有联通性。这提示我们使用并查集维护字符串（图中的点）的联通关系。直接套一个标准的不带权并查集模板就好了，我将标准不带权并查集封装成了一个 API 调用，这样遇到其他需要用并查集的题目也可直接使用。

在调用并查集模板之前，我们需要知道图中点的个数，那自然就是字符串的总数了。接下来，我们将字符串两两合并，这需要 $O(N^2)$ 的时间复杂度, 其中 n 为字符串总数。核心代码：

uf = UF(n)
for i in range(n):
      for j in range(i + 1, n):
           if strs[i] == strs[j] or is_similar(list(strs[i]), list(strs[j])):
              uf.union(i, j)
return uf.cnt

uf.cnt 为图中的联通分量的个数，正好对应题目的返回。

接下来，我们需要实现 is_similar 函数。 朴素的思路是遍历所有可能，即交换其中一个字符串（不妨称其为 s1）的任意两个字符。每次交换后都判断是否和另外一个字符串相等（不妨称其为 s2），代码表示其实 s1 == s2。由于每次判断两个字符相等的复杂度是线性的，因此这种算法 is_similar 的时间复杂度为 $O(m^3)$，其中 m 为字符串长度。这种算法会超时。

核心代码：

def is_similar(A, B):
    n = len(A)
    for i in range(n):
        for j in range(i + 1, n):
            A[i], A[j] = A[j], A[i]
            if A == B: return True
            A[i], A[j] = A[j], A[i]
    return False

实际上，我们只需要统计两个字符串不同字符的个数即可。这个不同字符指的是相同索引的字符不同。如果不同字符的个数等于 2 （或者 0）那么就可以认为两个字符串是相似的。

关键点

  • 判断两个字符串是否相似的函数 is_similar 没有必须真实交换并判断，而是判断不相等字符是否等于 2

代码

  • 语言支持：Python3

Python3 Code:

class UF:
  def __init__(self, M):
      self.parent = {}
      self.cnt = 0
      # 初始化 parent，size 和 cnt
      for i in range(M):
          self.parent[i] = i
          self.cnt += 1

  def find(self, x):
      if x != self.parent[x]:
          self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      return x
  def union(self, p, q):
      if self.connected(p, q): return
      leader_p = self.find(p)
      leader_q = self.find(q)
      self.parent[leader_p] = leader_q
      self.cnt -= 1
  def connected(self, p, q):
      return self.find(p) == self.find(q)

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        n = len(strs)
        uf = UF(n)
        def is_similar(A, B):
            n = len(A)
            diff = 0
            for i in range(n):
                if A[i] != B[i]: diff += 1
            return diff == 2

        for i in range(n):
            for j in range(i + 1, n):
                if strs[i] == strs[j] or is_similar(list(strs[i]), list(strs[j])):
                    uf.union(i, j)
        return uf.cnt

复杂度分析

令 n 为字符串总数，m 为字符串的平均长度。

  • 时间复杂度：$O(n^2\times m)$
  • 空间复杂度：$O(n)$

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。