字符串分组

标签: 位运算 并查集 字符串

难度: Hard

给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。

如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：

  • 往 s1 的字母集合中添加一个字母。
  • 从 s1 的字母集合中删去一个字母。
  • 将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。

数组 words 可以分为一个或者多个无交集的 组 。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组。

注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。

请你返回一个长度为 2 的数组 ans ：

  • ans[0] 是 words 分组后的 总组数 。
  • ans[1] 是字符串数目最多的组所包含的字符串数目。

示例 1：

输入：words = ["a","b","ab","cde"]
输出：[2,3]
解释：
- words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。所以 words[0] 与 words[1] 和 words[2] 关联。
- words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。所以 words[1] 与 words[0] 和 words[2] 关联。
- words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 关联。
- words[3] 与 words 中其他字符串都不关联。
所以，words 可以分成 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。

示例 2：

输入：words = ["a","ab","abc"]
输出：[1,3]
解释：
- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。
所以最大的组大小为 3 。

提示：

  • 1 <= words.length <= 2 * 104
  • 1 <= words[i].length <= 26
  • words[i] 只包含小写英文字母。
  • words[i] 中每个字母最多只出现一次。

Submission

运行时间: 649 ms

内存: 47.2 MB

class Solution:
    def groupStrings(self, words: List[str]) -> List[int]:
        n = len(words)
        words.sort(key=lambda w:len(w))
        fa = list(range(n))

        def find(x):
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]

        def union(x,y):
            fx, fy = find(x), find(y)
            fa[fx] = fy 

        aord = ord("a")
        visits = {}
        for i, word in enumerate(words):
            x = 0
            for c in word:
                x |= 1<<(ord(c) - aord)

            if x in visits:
                union(i, visits[x])
            else:
                visits[x] = i

                for j in range(26):
                    if x>>j & 1:
                        y = x ^ (1<<j)
                        if y in visits:
                            union(i,visits[y])
                        else:
                            visits[y] = i 

        for i in range(n):
            find(i)
        
        cnts = Counter(fa)
        return len(cnts), max(cnts.values())

Explain

这个题解使用了位掩码和并查集来将具有一定关联的字符串分组。首先，每个字符串被转换成一个整数位掩码，其中位掩码的第 i 位表示字符 'a'+i 是否出现在字符串中。这使得比较两个字符串是否只有一个字符的差异变得容易和快速。题解中先将字符串按长度排序，以便尽可能地减少比较次数。然后，使用一个字典来记录已经遇到的位掩码及其对应字符串的索引。对于每个位掩码，我们不仅记录它本身，还生成26个可能的通过增加或删除单个字母得到的位掩码，并尝试将当前字符串与这些位掩码所代表的字符串联合。这样可以确保所有只差一个字符的字符串都会被放入同一个组。最后，使用并查集来确定组成员，并统计最大组的大小。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def groupStrings(self, words: List[str]) -> List[int]:
        n = len(words) # 字符串的数量
        words.sort(key=lambda w:len(w)) # 按字符串长度排序
        fa = list(range(n)) # 初始化并查集数组

        def find(x):
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x] # 并查集查找

        def union(x,y):
            fx, fy = find(x), find(y)
            fa[fx] = fy  # 并查集合并

        aord = ord('a') # 字母'a'的ASCII码
        visits = {} # 存储已遇到的位掩码及其索引
        for i, word in enumerate(words):
            x = 0
            for c in word:
                x |= 1<<(ord(c) - aord) # 计算位掩码

            if x in visits:
                union(i, visits[x]) # 如果已经存在，合并到相同的组
            else:
                visits[x] = i # 记录当前位掩码和索引

                for j in range(26):
                    if x>>j & 1:
                        y = x ^ (1<<j) # 生成可能的位掩码变化
                        if y in visits:
                            union(i, visits[y]) # 如果变化后的位掩码存在，合并
                        else:
                            visits[y] = i # 记录变化后的位掩码和索引

        for i in range(n):
            find(i) # 更新所有节点的根节点，以完成所有合并操作

        cnts = Counter(fa) # 统计每个组的大小
        return [len(cnts), max(cnts.values())] # 返回总组数和最大组的大小

Explore

在这个题目中，我们的主要目的是判断字符串之间是否可以通过增加、删除或替换一个字符来互相转换，而不是完全一致的匹配。使用位掩码来表示每个字符是否出现（而非出现次数），可以快速比较两个字符串的组成差异。这种方法简化了逻辑，并有效地支持了只通过单一字符变化达到的分组需求，因为字符的具体出现次数在这种变化检测中不是必要的。

题解中生成位掩码的变化主要通过位操作实现。对于每个字符的位，我们尝试将其翻转（即从1变为0或从0变为1），代表删除或添加一个字符。这样的位操作确保了可以覆盖所有可能通过单一字符变化形成的位掩码。通过这种方法，我们可以确保所有只差一个字符的变化都被检测到，并正确地将相关字符串进行分组。

按字符串长度排序的主要目的是尽量减少不必要的比较。理论上，长度差异较大的字符串不太可能通过单一字符的增加、删除或替换来匹配，因此先比较长度相近的字符串可以提高效率。然而，如果输入数据中大部分字符串长度接近，这种排序可能不会显著减少比较次数，因为几乎每个字符串都需要与其他字符串进行比较。

并查集在这个题解中用于管理和追踪字符串分组。每次当两个字符串确定只通过一个字符的增加、删除或替换可以互相转换时，这两个字符串就通过并查集的union操作合并到同一个组。并查集通过维护每个节点的父节点来形成一个树状结构，从而确保一旦两个字符串被合并到同一个组，它们将始终保持在同一组内。通过对所有字符串执行find操作，我们可以更新它们的根节点，最终得到一个准确的分组结果，确保每个组内的字符串都是相互关联的，而与其他组的字符串无关。