0839. 相似字符串组

题目地址(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 啦。

最后更新于