按字典序排列最小的等效字符串

标签: 并查集 字符串

难度: Medium

给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。

其中  s1[i] 和 s2[i]  是一组等价字符。

  • 举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

等价字符遵循任何等价关系的一般规则：

  •  自反性 ：'a' == 'a'
  •  对称性 ：'a' == 'b' 则必定有 'b' == 'a'
  •  传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'

例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。

示例 1：

输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。

示例 2：

输入：s1 = "hello", s2 = "world", baseStr = "hold"
输出："hdld"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。

示例 3：

输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
输出："aauaaaaada"
解释：我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 组，因此 S 中除了 'u' 和 'd' 之外的所有字母都转化成了 'a'，最后答案为 "aauaaaaada"。

提示：

  • 1 <= s1.length, s2.length, baseStr <= 1000
  • s1.length == s2.length
  • 字符串s1, s2, and baseStr 仅由从 'a' 到 'z' 的小写英文字母组成。

Submission

运行时间: 31 ms

内存: 16.1 MB

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]

    def find(self, x):
        if x != self.root[x]:
            # 在查询的时候合并到顺带直接根节点
            root_x = self.find(self.root[x])
            self.root[x] = root_x
            return root_x
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if root_x < root_y:
            root_x, root_y = root_y, root_x
        self.root[root_x] = root_y
        return


class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        n = len(s1)
        uf = UnionFind(26)
        for i in range(n):
            uf.union(ord(s1[i]) - ord("a"), ord(s2[i]) - ord("a"))
        ans = ""
        for w in baseStr:
            ans += chr(uf.find(ord(w) - ord("a")) + ord("a"))
        return ans

Explain

本题使用并查集(Union-Find)数据结构来解决字符等价的问题。并查集是一种有效管理元素分组关系的数据结构，特别适合处理动态连通性问题。首先，初始化一个大小为26的并查集，代表26个英文字母。遍历s1和s2中的字符，将每对等价字符联合在一起。这样，所有传递性等价的字符都会被归入同一个集合。在处理完所有等价关系后，对于baseStr中的每个字符，查找其所属的集合代表（即最小字典序的字符），并构建最终的结果字符串。

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

空间复杂度: O(1)

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]  # 初始化每个字母的根节点

    def find(self, x):
        if x != self.root[x]:
            root_x = self.find(self.root[x])  # 查找根节点
            self.root[x] = root_x  # 路径压缩
            return root_x
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if root_x < root_y:
                root_x, root_y = root_y, root_x  # 保证小的根节点作为代表
            self.root[root_x] = root_y  # 合并集合


class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        n = len(s1)
        uf = UnionFind(26)  # 初始化并查集
        for i in range(n):
            uf.union(ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a'))  # 处理等价关系
        ans = ''
        for w in baseStr:
            ans += chr(uf.find(ord(w) - ord('a')) + ord('a'))  # 查找并构建结果字符串
        return ans

Explore

在并查集的实现中，确保在union操作时总是将字典序较小的字符作为代表，可以通过比较两个字符的根节点的字典序来实现。首先，使用`find`函数确定每个字符的根节点。然后，在`union`函数中，比较这两个根节点所代表的字符的字典序，将字典序较大的根节点指向字典序较小的根节点。这样，较小字典序的字符始终作为代表，从而保证了集合中的代表是字典序最小的字符。

并查集通过其设计本质上支持处理等价类的传递性关系。当处理诸如'A == B', 'B == C', 'A == D'等关系时，通过逐对调用`union`操作，确保每个字符与其等价的字符连接。例如，首先连接'A'和'B'，然后'B'和'C'，接着由于'A'和'B'已连接，'A'与'C'也会通过'B'连接起来。最后，'A'与'D'的连接直接加入这个集合。因此，所有等价的字符都会逐渐形成一个组或集合，其中任何一个字符都可以通过根节点或中间节点连接到任何其他字符。

路径压缩技术是在执行find操作时应用的，其目的是将查找路径上的每个节点直接连接到根节点，从而减少后续查找操作的深度和时间。这种优化虽然改变了树的深度，但不会影响union操作的基本效率。在执行union操作时，先通过find操作找到各自的根节点，并进行合并。由于find操作已经进行了路径压缩，因此union操作也会间接受益，因为合并操作涉及到的树高度较低，从而保持了高效率。维护路径压缩的效果主要是在find操作中实现，而union操作继续保证了结构的正确性和效率。

在题解中，每个字符的初始根节点是其自身，这意味着每个字符最初都是自己的代表。如果baseStr中的某个字符在s1和s2中没有出现，即没有任何等价关系影响这个字符，这个字符将简单地被视为与自身等价。因此，当查找这种字符的代表时，会发现其代表仍然是自身。这样，算法不仅处理了在s1和s2中定义的等价关系，也自然处理了自反性的情况，确保对于baseStr中未出现的字符，算法仍然有效且这些字符简单地映射到自身。