面试题 17.07. 婴儿名字

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择 字典序最小 的名字作为真实名字。

示例：

输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]

提示：

• names.length <= 100000

Python 解答：

class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
        def find(x):
                return x if alis[x] == x else find(alis[x])
        adic = {}
        bdic = {}
        i = 0
        total = 0
        for item in names:
            x, y = item.split('(')
            total += int(y[:-1])
            if x not in adic.keys():
                adic[x] = i
                bdic[i] = x
                i += 1
        for item in synonyms:
            x, y = item.split(',')
            x = x[1:]
            y = y[:-1]
            if x not in adic.keys():
                adic[x] = i
                bdic[i] = x
                i += 1
            if y not in adic.keys():
                adic[y] = i
                bdic[i] = y
                i += 1
        alis = [j for j in range(i)]
        for item in synonyms:
            x, y = item.split(',')
            x = x[1:]
            y = y[:-1]
            one = find(adic[x])
            two = find(adic[y])
            if bdic[one] < bdic[two]:
                alis[two] = one
            else:
                alis[one] = two
        res = [0 for j in range(i)]
        for item in names:
            first, second = item.split('(')
            second = second[:-1]
            index = find(adic[first])
            res[index] += int(second)
        return [key+'('+str(res[value])+')' for key, value in adic.items() if res[value] != 0]