点击获取AI摘要

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

给出长度相同的两个字符串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' 的小写英文字母组成。

问题分析

给定长度相同的两个字符串 s1 和 s2，以及一个字符串 baseStr，其中对于任意索引 i，s1[i] 与 s2[i] 构成一对等价字符。等价关系须满足自反性、对称性和传递性。也就是说，当 a == b 并且 b == c 时，则必然有 a == c。因此可以将所有字母划分为若干等价类，每个等价类中的任意两个字母都相互等价。对 baseStr 中的每个字符，都可以用其所属等价类中“字典序最小”的字符来替换，从而得到整体字典序最小的结果字符串。

等价关系需要处理传递性，直接遍历所有字母对并检查传递关系会导致较高复杂度。并查集（Union-Find）结构在处理动态等价关系时非常高效，可以用来合并等价字符并快速查询某个字符所属的等价类的“代表元”（即根节点）。我们要保证每个等价类的根节点恰好是该类中字典序最小的字符，这样对 baseStr 中的每个字符直接取其根节点即可得到最小等价字符。

算法思路

并查集初始化
- 创建大小为 26 的数组 parent[0..25]，表示字母 'a'~'z' 的父节点映射，初始时 parent[i] = i，即每个字母自成一棵树，自己是自己的根。
定义并查集操作
- find(x)：当 parent[x] != x 时，递归调用 find(parent[x]) 并进行路径压缩：
  1
  2
  3
  if parent[x] != x:
  parent[x] = find(parent[x])
  return parent[x]
  这样能将路径上的所有节点直接指向根节点，加速后续查找。
- union(x, y)：先分别 find(x) 得到 rx，再 find(y) 得到 ry。若 rx != ry，则将字典序大的根指向字典序小的根。由于字母用 0~25 表示，数值越小字典序越小，故：
  1
  2
  3
  4
  if rx < ry:
  parent[ry] = rx
  else:
  parent[rx] = ry
  保证合并后，该等价类的根节点始终是类中最小字母。
合并等价对
- 遍历 s1 与 s2 的每个位置 i，令 a = ord(s1[i]) - ord('a')，b = ord(s2[i]) - ord('a')，执行 union(a, b)。此时会将所有间接等价关系逐步合并，最终每个等价类形成一棵以字典序最小字母为根的树。
构造最小等价字符串
- 遍历 baseStr 中的每个字符 c，计算索引 idx = ord(c) - ord('a')，调用 find(idx) 得到根节点 r，表示该字符在等价类中可替换为字典序最小的字符 chr(r + ord('a'))。将所有替换结果拼接成最终字符串。

时间复杂度

合并操作进行 len(s1) 次 union，令 $n = \lvert s1\rvert$ 。每次 union 实际内部有两次 find，均摊时间近似 $O(\alpha(26))$ ，其中 $\alpha(\cdot)$ 为反阿克曼函数，在字母规模下可视为常数。因此合并总开销约为
$O\bigl(n \times \alpha(26)\bigr)\approx O(n).$
构造最终答案需对 baseStr 中每个字符做一次 find，令 $m = \lvert baseStr\rvert$ ，时间约为
$O\bigl(m \times \alpha(26)\bigr)\approx O(m).$
整体时间复杂度：
$O(n + m).$
空间复杂度：仅需维护大小为 26 的 parent 数组，记为 $O(1)$ ；另需输出结果字符串占用 $O(m)$ 空间。

代码分解

并查集初始化
1
parent = [i for i in range(26)]
- 创建长度为 26 的列表，parent[i] = i。

定义 find 函数（带路径压缩）

def find(x: int) -> int:
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

定义 union 函数

def union(x: int, y: int) -> None:
    rx = find(x)
    ry = find(y)
    if rx == ry:
        return
    if rx < ry:
        parent[ry] = rx
    else:
        parent[rx] = ry

先找到 x、y 的根节点 rx、ry；若不同，则将数值较大的根挂到较小根之下，保证根是等价类中字典序最小字符。

合并 s1 与 s2 的等价对

for a_char, b_char in zip(s1, s2):
    a_idx = ord(a_char) - ord('a')
    b_idx = ord(b_char) - ord('a')
    union(a_idx, b_idx)

遍历每对等价字符，调用 union 完成合并。

构造结果字符串

result_chars = []
for c in baseStr:
    idx = ord(c) - ord('a')
    root = find(idx)
    result_chars.append(chr(root + ord('a')))
return "".join(result_chars)

对 baseStr 每个字符 c，找到其等价类的最小根 root 并转换回字符，拼接到结果列表，最后合并成字符串。

代码实现

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        # 1. 并查集初始化：parent[i] = i 表示字母 chr(i + ord('a'))
        parent = [i for i in range(26)]
        
        # 2. 定义 find 函数（带路径压缩）
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # 3. 定义 union 函数：让较小字母序的根成为合并后根
        def union(x: int, y: int) -> None:
            rx = find(x)
            ry = find(y)
            if rx == ry:
                return
            # 根节点用数值（0..25）表示，数值越小，字典序越小
            if rx < ry:
                parent[ry] = rx
            else:
                parent[rx] = ry
        
        # 4. 根据 s1 和 s2 中的对应关系做合并
        for a_char, b_char in zip(s1, s2):
            a_idx = ord(a_char) - ord('a')
            b_idx = ord(b_char) - ord('a')
            union(a_idx, b_idx)
        
        # 5. 构造结果：baseStr 中每个字符替换为其等价类的最小代表
        result_chars = []
        for c in baseStr:
            idx = ord(c) - ord('a')
            root = find(idx)
            result_chars.append(chr(root + ord('a')))
        
        return "".join(result_chars)