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

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里
标签
字符串 并查集

题目描述

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

image-20260929073603307

image-20260929073603410

题意分析

s1 与 s2 相同位置的两个小写字母互相等效，这种关系还具有传递性。可以把 baseStr 中每个字母替换成与它等效的任意字母，求能得到的字典序最小字符串。

每个位置可以独立替换，不是在原字符串中交换字符，也不受原有字符数量限制。没有参与任何等价关系的字母仍与自身等效，可以保持不变。

解法：并查集合并连通块

核心思路

[!blue]

成对等价关系经过传递后，会把字母分成若干等价类。同一类中的字母都能互相替换，所以只要知道每个字母所属的类，以及这一类中最小的字母，就能决定它的最优替换。

用并查集维护这些类，每个字母最初单独成组。处理一对关系时，先找到两个字母各自的根。如果根不同，就把较大的根连接到较小的根；这样根不仅代表集合，还始终是集合里的最小字母。

这个最小代表性质可以逐次保持：初始单元素集合显然成立；合并时两个旧根分别已经是各自集合最小值，更小的那个自然也是合并后整个集合的最小值。路径压缩只是让中间节点直接指向同一根，不改变这个代表。

全部关系合并完后，对 baseStr 每个字符查找最终根，转换回相应字母即可。不能只读取一次 parent[x]，因为它可能仍是中间父节点，只有完整查根才能得到最新的最小代表。

各位置可选字符互不影响，所以每一位都换成所属类最小值会得到全局字典序最小。与任何不同结果比较，在第一处不同的位置，本方案已经选了该位置能取的最小字母，不可能比对方更大。

解题步骤

  1. 初始化 26 个父指针，令每个字母指向自身。
  2. 逐对读取 s1[i]、s2[i]，通过 find 得到它们的根。
  3. 根不同时，把较大根挂到较小根下面；查找过程中使用路径压缩。
  4. 所有关系处理完后，再逐字符查询 baseStr 的最终根，并把根下标转回字母。
  5. 将替换字符按原位置顺序组成答案。

代码实现

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int[] parent = new int[26];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < s1.length(); i++) {
            int root1 = find(parent, s1.charAt(i) - 'a');
            int root2 = find(parent, s2.charAt(i) - 'a');

            if (root1 != root2) {
                // 把较大根挂到较小根下，根始终是组内最小字母。
                parent[Math.max(root1, root2)] = Math.min(root1, root2);
            }
        }

        // 全部关系合并完后，再逐个查找最终的最小代表。
        StringBuilder answer = new StringBuilder(baseStr.length());

        for (int i = 0; i < baseStr.length(); i++) {
            int root = find(parent, baseStr.charAt(i) - 'a');

            answer.append((char) ('a' + root));
        }

        return answer.toString();
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            // 路径压缩只缩短路径，不改变集合代表。
            parent[x] = find(parent, parent[x]);
        }

        return parent[x];
    }
}

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
    parent := make([]int, 26)
    for i := range parent {
        parent[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            // 路径压缩只缩短路径，不改变集合代表。
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    for i := 0; i < len(s1); i++ {
        root1 := find(int(s1[i] - 'a'))
        root2 := find(int(s2[i] - 'a'))
        // 把较大根挂到较小根下，根始终是组内最小字母。
        if root1 < root2 {
            parent[root2] = root1
        } else if root2 < root1 {
            parent[root1] = root2
        }
    }

    // 全部关系合并完后，再逐个查找最终的最小代表。
    answer := make([]byte, len(baseStr))
    for i := range baseStr {
        root := find(int(baseStr[i] - 'a'))
        answer[i] = byte(root) + 'a'
    }
    return string(answer)
}

复杂度分析

  • 时间复杂度：$O(n+m)$，n 为关系串长度，m 为 baseStr 长度；并查集固定只有 26 个节点。
  • 空间复杂度：$O(m+26)$，固定并查集之外，Java 的 StringBuilder 和 Go 的字节缓冲都占 $O(m)$；即使不计最终返回字符串，也不能忽略这些构造缓冲。

关键点总结

[!green]

  • 并查集负责等价关系的传递闭包，较小根规则同时维护每个类的最小字符。
  • 合并的是两个集合的根，避免只移动一个中间节点而破坏已经建立的关系。
  • 先完成全部合并，再输出最终代表，后面的等价关系也能影响前面出现过的字符。

易错点总结

[!yellow]

  • 任意选择根只保证类成员连通，不能保证根字母最小；本写法需要始终让较小根成为代表。
  • 直接修改原字符的父节点而不先查根，可能没有真正合并两个完整集合。
  • 输出直接父节点而不是调用 find，可能停在尚未压缩的中间代表上。
  • 忘记初始化 parent[i] = i，默认零会错误地把所有字母都归到 a。
  • 一边读取关系一边把输出结果固定下来，后续合并可能带来更小的等价字母。
  • 像字符交换题一样保留原有频次，会额外限制本题允许的独立替换。

相似题目

题目 难度 关联与区别
990. 等式方程的可满足性 中等 同样先用并查集合并等价字母，本题还把每个分量的最小字母作为替换代表。
1202. 交换字符串中的元素 中等 原题只能重排已有位置的字符，需要保留频次，本题可直接把字符换成等价类的最小代表。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/72842458
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！