LeetCode 面试题 17.07. 婴儿名字

2022-07-18 HGNULB 约 11 分钟

文章信息 8 个分类 · 7 个标签

分类

LeetCode CodeTop 中等 未解决 2-5 快手 腾讯 程序员面试金典（第 6 版）

标签

数组 字符串 哈希表 深度优先搜索 广度优先搜索 并查集 计数

目录 收起 展开

题目描述

✅ 面试题 17.07. 婴儿名字

题意分析

输入是两份数据：names 里每个元素形如 John(15)，把一个名字和它的登记次数打包成字符串；synonyms 里每个元素形如 (Jon,John)，声明这两个写法指向同一个真实名字。

要输出的是「合并后的真实名字表」：属于同一个真实名字的所有写法，次数要加在一起，并且只用其中字典序最小的那个写法作为对外的代表。

关键约束信号有两个。其一，同名关系会传递：Jon 等于 John、John 等于 Johnny，那么 Jon 和 Johnny 也必须算作同一个人，题目并不会把传递后的关系再显式列一遍。其二，字符串总长可以到十万级，说明每对同名关系只允许被处理常数次，不能反复扫描 synonyms 做闭包。

边界要提前想清楚。synonyms 里出现的名字未必在 names 里登记过，这种名字次数为零，即使它字典序更小也不能凭空造出一条输出；反过来，names 里的名字也可能一条同名关系都没有，它自己就是一组。输出的顺序题目不作要求，但每组的代表名字和求和结果必须唯一确定。

解法：并查集合并同义词

核心思路

先想最直接的做法：对每个名字反复扫一遍 synonyms，把能连上的名字并进当前集合，直到集合不再变大，再从集合里挑字典序最小的名字输出。这等于手工求传递闭包，一个名字最坏要扫 $m$ 轮，总代价退化到 $O(nm)$，而且写起来还得小心重复访问。

瓶颈在于「等价关系」被当成了一次性的查询反复重算。但同名关系天然满足自反、对称、传递三条性质，这正是一个等价关系，而维护等价关系的划分只需要一个并查集：每来一对同义词就做一次合并，查询时一次 find 就能问出所属的组。

剩下的问题是代表元怎么选。并查集默认按秩或按大小合并，根是谁完全取决于合并顺序，靠不住。这里改成「按字典序合并」，并维持一条不变量：任意时刻，每个连通分量的根都是该分量内所有名字中字典序最小的那个。合并两棵树时比较的必须是两个根而不是两个原始名字，把字典序大的根挂到小的根下面；由于两个根分别是各自分量的最小值，合并后的最小值必然是二者中较小的那个，不变量得以保持。

有了这条不变量，最后只需遍历频次表，把每个名字的次数加到 find(name) 上，累加结果自然就落在字典序最小的代表名字上。只遍历 names 而不遍历所有出现过的名字，也就顺带排除了那些次数为零的同义词写法。

解题步骤

• 扫描 names，对每个元素定位左右括号，切出名字和括号内的数字，存进频次表 countMap。为什么要先解析：后面所有操作都以「名字」为单位，字符串外壳只在这一步剥掉一次。
• 扫描 synonyms，对每个元素去掉首尾括号、按逗号切成两个名字，对它们做一次 union。为什么可以边读边合并：并查集不要求先知道全部元素，find 时懒初始化即可。
• union 内部先各自 find 出两个根，相同则直接返回；不同则比较两个根的字典序，把大的挂到小的下面。为什么比较根而不是参数本身：只有根才代表整个分量当前的最小值，比较参数会让不变量在多次合并后失效。
• 再遍历一次 countMap，对每个名字求根，把次数累加进 sumMap[root]。为什么必须重新 find：合并是持续发生的，第一步记下的归属早就过期了，必须在全部合并完成后统一查询。
• 把 sumMap 里的每一项拼回 名字(次数) 的格式返回。为什么可以跳过零值：names 中不会登记次数为零的名字，这条判断只是对异常输入的兜底。

以 names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"]、synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"] 走一遍：解析后 countMap 为 John=15, Jon=12, Chris=13, Kris=4, Christopher=19。处理 (Jon,John)，两者的根就是自身，John < Jon，于是 parent[Jon]=John。处理 (John,Johnny)，根分别是 John 与 Johnny，John 是 Johnny 的前缀且更短故更小，parent[Johnny]=John。处理 (Chris,Kris)，Chris < Kris，parent[Kris]=Chris。处理 (Chris,Christopher)，Chris 是前缀更短更小，parent[Christopher]=Chris。此时两棵树的根分别是 John 和 Chris，都符合「根是分量内字典序最小」。累加阶段：John 求根得 John，sumMap[John]=15；Jon 求根经一次跳转得 John，sumMap[John]=27；Chris 求根得 Chris，sumMap[Chris]=13；Kris 求根得 Chris，sumMap[Chris]=17；Christopher 求根得 Chris，sumMap[Chris]=36。注意 Johnny 从未出现在 countMap 中，因此不会产生 Johnny(0) 这样的多余输出。最终返回 ["John(27)","Chris(36)"]。

代码实现

// 用并查集把同义词连接为同一连通分量，并将字典序最小的名字作为根，保证输出稳定。
class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        Map<String, Integer> countMap = new HashMap<>();
        for (String item : names) {
            int left = item.indexOf('(');
            int right = item.indexOf(')');
            String name = item.substring(0, left);
            int count = Integer.parseInt(item.substring(left + 1, right));
            countMap.put(name, count);
        }

        UnionFind uf = new UnionFind();
        for (String pair : synonyms) {
            int comma = pair.indexOf(',');
            String a = pair.substring(1, comma);
            String b = pair.substring(comma + 1, pair.length() - 1);
            uf.union(a, b);
        }

        Map<String, Integer> sumMap = new HashMap<>();
        for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
            String root = uf.find(entry.getKey());
            sumMap.put(root, sumMap.getOrDefault(root, 0) + entry.getValue());
        }

        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : sumMap.entrySet()) {
            if (entry.getValue() == 0) {
                continue;
            }
            res.add(entry.getKey() + "(" + entry.getValue() + ")");
        }

        return res.toArray(new String[0]);
    }

    static class UnionFind {
        private final Map<String, String> parent = new HashMap<>();

        String find(String x) {
            parent.putIfAbsent(x, x);
            String p = parent.get(x);
            if (!p.equals(x)) {
                parent.put(x, find(p));
            }
            return parent.get(x);
        }

        void union(String a, String b) {
            String pa = find(a);
            String pb = find(b);
            if (pa.equals(pb)) {
                return;
            }

            if (pa.compareTo(pb) < 0) {
                parent.put(pb, pa);
            } else {
                parent.put(pa, pb);
            }
        }
    }
}

// 用并查集把同义词连接为同一连通分量，并将字典序最小的名字作为根，保证输出稳定。
func trulyMostPopular(names []string, synonyms []string) []string {
    countMap := map[string]int{}
    for _, item := range names {
        left := strings.IndexByte(item, '(')
        right := strings.IndexByte(item, ')')
        name := item[:left]
        cnt, _ := strconv.Atoi(item[left+1 : right])
        countMap[name] = cnt
    }

    uf := newUnionFind()
    for _, pair := range synonyms {
        comma := strings.IndexByte(pair, ',')
        a := pair[1:comma]
        b := pair[comma+1 : len(pair)-1]
        uf.union(a, b)
    }

    sumMap := map[string]int{}
    for name, cnt := range countMap {
        root := uf.find(name)
        sumMap[root] += cnt
    }

    res := make([]string, 0, len(sumMap))
    for name, cnt := range sumMap {
        if cnt == 0 {
            continue
        }
        res = append(res, fmt.Sprintf("%s(%d)", name, cnt))
    }

    return res
}

type unionFind struct {
    parent map[string]string
}

func newUnionFind() *unionFind {
    return &unionFind{parent: make(map[string]string)}
}

func (u *unionFind) find(x string) string {
    if p, ok := u.parent[x]; ok {
        if p != x {
            u.parent[x] = u.find(p)
        }
        return u.parent[x]
    }
    u.parent[x] = x
    return x
}

func (u *unionFind) union(a, b string) {
    pa := u.find(a)
    pb := u.find(b)
    if pa == pb {
        return
    }

    if pa < pb {
        u.parent[pb] = pa
    } else {
        u.parent[pa] = pb
    }
}

复杂度分析

• 时间复杂度：$O((n+m)\alpha(k))$，其中 $n$ 是 names 长度，$m$ 是 synonyms 长度，$k$ 是出现过的不同名字数。凭据：解析、合并、累加各扫一遍输入，每个元素只做常数次并查集操作，路径压缩加按字典序合并使单次操作摊还为反阿克曼函数级别；此处把字符串的哈希与比较视作常数代价，若计入长度 $L$ 还要乘上一个 $O(L)$ 因子。
• 空间复杂度：$O(k)$，凭据：频次表、并查集的父指针表、求和表都以不同名字为键，各存不超过 $k$ 项，递归求根的栈深也被路径压缩压在同一量级内。

关键点总结

• 「传递的等价关系」是并查集最标准的触发信号：题目只给出相邻的两两关系，却要求按整组处理，就该想到把关系合并成划分，而不是逐个求闭包。
• 代表元不是随便选的。当题目对输出的代表有额外要求（字典序最小、编号最小、值最小）时，就把这个要求写成合并规则，并明确写下「根即最优」这条不变量。
• 合并时永远比较两个根，不是两个参数。这是把「按秩合并」改成「按业务序合并」时最容易翻车的地方。
• 统计必须在所有合并完成之后再做一次 find，中途缓存的归属一定过期。这条在带权并查集、账户合并一类题里同样适用。
• 面试视角：这题的隐藏考点其实是字符串解析和输出集合的确定，面试官常追问「同义词里出现但没登记次数的名字要不要输出」。答案是不输出，因为只遍历 names 就自动排除了；能主动说出这一点比写对并查集更能拉开分数。
• 面试视角：若被追问「不用并查集怎么做」，正确回答是把名字建成无向图后跑一遍遍历取连通分量，时间同样接近线性，但需要显式建图和访问标记，代码量更大——能给出替代方案并说清取舍，说明是真理解而非套模板。

易错点总结

• 错误写法：在 union 里直接比较传入的 a 与 b 的字典序来决定谁当根。用例 synonyms = ["(Jon,John)","(Johnny,Jon)"] → 第二次合并时 Johnny 与 Jon 比较得 Johnny 更小，把已经是根的 John 挂到 Johnny 下，最终代表变成 Johnny，不是分量内字典序最小的 John。
• 错误写法：沿用默认的按秩或按大小合并，最后再从每组里找最小名字。用例任意含三个以上写法的同义词组 → 根取决于合并顺序，若不额外遍历整组求最小值，输出的代表名就是错的。
• 错误写法：在解析 synonyms 时忘记剥掉首尾括号，直接按逗号切分。用例 "(Jon,John)" → 得到 (Jon 和 John)，这两个带括号的串与 names 里的名字永远对不上，所有同义词关系全部失效。
• 错误写法：把所有在并查集里出现过的名字都拿去输出。用例 synonyms 含 (John,Johnny) 而 names 里没有 Johnny → 多出一条 Johnny(0)，答案数量对不上。
• 错误写法：先算好每个名字的根缓存起来，再一边合并一边累加。用例合并顺序为 (Chris,Kris) 在 (Chris,Christopher) 之前而累加在中间发生 → 早查到的根随后被改写，次数落在过期的代表上，同一组被拆成两条输出。
• 错误写法：把次数加到名字自己头上而不是根上，指望最后再合并。用例 John(15) 与 Jon(12) → 输出成 John(15) 与 Jon(12) 两条，没有完成求和。
• 错误写法：find 只顺着父指针往上走却不做路径压缩。用例把一万个名字连成一条链式的同义词序列 → 每次查询退化成 $O(k)$，总代价来到平方级别，大数据点超时。
• 错误写法：解析 names 时用固定下标或按空格切分假定名字长度。用例 Christopher(19) → 名字长度不固定，只能靠 ( 与 ) 的位置切分，否则数字被截断成错误的次数。
• 错误写法：拼接结果时漏掉括号或写成 名字:次数。用例 John 与 27 → 返回 John27，格式不符判定失败，这是本题最容易被忽略的低级失分点。
• 错误写法：Java 里用 != 而不是 equals 比较名字，例如把终止条件写成 parent.get(x) != x。用例任何由 substring 切出来的名字 → 内容相同但对象不同，根节点也被判成「还没到顶」，find 无限递归直到栈溢出。

相似题目

题目	难度	考察点
323. 无向图中连通分量的数目	中等	只数分量个数，不需要选代表元
547. 省份数量	中等	输入是邻接矩阵，需先还原出待合并的边
684. 冗余连接	中等	用合并失败来定位成环的那条边
721. 账户合并	中等	同样是字符串归组，但组内还要排序去重
765. 情侣牵手	困难	由分量大小反推最少交换次数
839. 相似字符串组	困难	关系不是给定的，要两两判定相似后再合并
990. 等式方程的可满足性	中等	先合并等式再用不等式检验矛盾
1202. 交换字符串中的元素	中等	分量内字符可任意重排，要组内排序求最小串
LCR 116. 省份数量	中等	省份数量的同题换皮，可用于对比建图写法
LCR 117. 相似字符串组	困难	相似字符串组的同题换皮，练习判定与合并分离
LCR 118. 冗余连接	中等	冗余连接的同题换皮，练习环检测