面试题 17.07. 婴儿名字

class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
        mp = defaultdict(int)
        p = defaultdict(str)

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def union(a, b):
            pa, pb = find(a), find(b)
            if pa == pb:
                return
            if pa > pb:
                mp[pb] += mp[pa]
                p[pa] = pb
            else:
                mp[pa] += mp[pb]
                p[pb] = pa

        for e in names:
            idx = e.find("(")
            name, w = e[: idx], int(e[idx + 1: -1])
            mp[name] = w
            p[name] = name
        for e in synonyms:
            idx = e.find(",")
            name1, name2 = e[1: idx], e[idx + 1: -1]
            mp[name1] += 0
            mp[name2] += 0
            p[name1] = name1
            p[name2] = name2

        for e in synonyms:
            idx = e.find(",")
            name1, name2 = e[1: idx], e[idx + 1: -1]
            union(name1, name2)
        return [f'{name}({mp[name]})' for name, w in mp.items() if name == find(name)]

class Solution {
    private Map<String, Integer> mp = new HashMap<>();
    private Map<String, String> p = new HashMap<>();

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        for (String e : names) {
            int idx = e.indexOf("(");
            String name = e.substring(0, idx);
            int w = Integer.parseInt(e.substring(idx + 1, e.length() - 1));
            mp.put(name, w);
            p.put(name, name);
        }
        for (String e : synonyms) {
            int idx = e.indexOf(",");
            String name1 = e.substring(1, idx);
            String name2 = e.substring(idx + 1, e.length() - 1);
            if (!mp.containsKey(name1)) {
                mp.put(name1, 0);
            }
            if (!mp.containsKey(name2)) {
                mp.put(name2, 0);
            }
            p.put(name1, name1);
            p.put(name2, name2);
        }
        for (String e : synonyms) {
            int idx = e.indexOf(",");
            String name1 = e.substring(1, idx);
            String name2 = e.substring(idx + 1, e.length() - 1);
            union(name1, name2);
        }
        List<String> t = new ArrayList<>();
        for (Map.Entry<String, Integer> e : mp.entrySet()) {
            String name = e.getKey();
            if (Objects.equals(name, find(name))) {
                t.add(name + "(" + e.getValue() + ")");
            }
        }
        String[] res = new String[t.size()];
        for (int i = 0; i < res.length; ++i) {
            res[i] = t.get(i);
        }
        return res;
    }

    private String find(String x) {
        if (!Objects.equals(p.get(x), x)) {
            p.put(x, find(p.get(x)));
        }
        return p.get(x);
    }

    private void union(String a, String b) {
        String pa = find(a), pb = find(b);
        if (Objects.equals(pa, pb)) {
            return;
        }
        if (pa.compareTo(pb) > 0) {
            mp.put(pb, mp.getOrDefault(pb, 0) + mp.getOrDefault(pa, 0));
            p.put(pa, pb);
        } else {
            mp.put(pa, mp.getOrDefault(pa, 0) + mp.getOrDefault(pb, 0));
            p.put(pb, pa);
        }
    }
}