每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
如果每个名称都映射到其替代拼写的列表，那么在将 X 和 Y 设置为同义词时，你可能需要更新许多列表。如果 X 是{A, B, C}的同义词，而 Y 是{D, E, F}的同义词，那么你需要将{Y, D, E, F}添加到 A 的同义词列表、B 的同义词列表、C 的同义词列表和 X 的同义词列表中。{Y, D, E, F}同理。有更快的方法么?
提示 6
相反，X、A、B 和 C 应该映射到同一个集合{X, A, B, C}。Y、D、E 和 F 应该映射到同一个集合{Y, D, E, F}。当我们将 X 和 Y 设置为同义词时，可以将其中一个集合复制到另一个集合中(例如，将{Y, D, E, F}添加到{X, A, B, C}中)。散列表还需进行其他更改么?
提示 7
另一种方法是把它看作一幅图。应该怎么做?
提示 8
可以把将 X, Y 记为同义词看作是在 X 节点和 Y 节点之间添加一条边。那么如何算一组同义词有哪些呢?
提示 9
每个连通子图表示一组同义词。要找到每个组，可以重复广度优先(或深度优先)搜索。
评论 (0)
《程序员面试金典（第 6 版）》独家授权
本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。
