LeetCode 面试题 17.07. 婴儿名字

Categories:

题目描述
思路分析
1. 解法一：并查集合并同义词（推荐）
2. 解法二：图遍历分组
相似题目

题目描述

✅ 面试题 17.07. 婴儿名字

思路分析

解法一：并查集合并同义词（推荐）

核心思路：

解析 name(count) 构建名字频次表。

用并查集把同义词连接为同一连通分量，并将字典序最小的名字作为根，保证输出稳定。

遍历频次表，把每个名字的计数累加到其根节点。

汇总后输出 root(sum)；若某分量总数为 0 则不输出。

复杂度分析：

时间复杂度：O((n + m) · α(k))，其中 n 为名字数量，m 为同义词数量，k 为不同名字总数。

空间复杂度：O(k)，其中 k 为不同名字总数。

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);
            }
        }
    }
}

import (
	"fmt"
	"strconv"
	"strings"
)

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: 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
	}
}

解法二：图遍历分组

核心思路：

把同义词当成无向边，构建名字图。

对每个未访问的名字做 DFS/BFS，统计连通分量内总频次。

取该分量中字典序最小的名字作为代表，输出 name(sum)。

复杂度分析：

时间复杂度：O(k + m)，其中 k 为不同名字总数，m 为同义词数量。

空间复杂度：O(k + m)，其中 k 为不同名字总数。

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);
        }

        Map<String, List<String>> graph = new HashMap<>();
        for (String pair : synonyms) {
            int comma = pair.indexOf(',');
            String a = pair.substring(1, comma);
            String b = pair.substring(comma + 1, pair.length() - 1);
            graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
            graph.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
        }

        Set<String> visited = new HashSet<>();
        List<String> res = new ArrayList<>();
        for (String name : graph.keySet()) {
            if (visited.contains(name)) {
                continue;
            }

            Deque<String> stack = new ArrayDeque<>();
            stack.push(name);
            visited.add(name);

            int sum = 0;
            String best = name;

            while (!stack.isEmpty()) {
                String cur = stack.pop();
                sum += countMap.getOrDefault(cur, 0);
                if (cur.compareTo(best) < 0) {
                    best = cur;
                }

                for (String next : graph.getOrDefault(cur, List.of())) {
                    if (visited.add(next)) {
                        stack.push(next);
                    }
                }
            }

            if (sum > 0) {
                res.add(best + "(" + sum + ")");
            }
        }

        for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
            if (graph.containsKey(entry.getKey())) {
                continue;
            }
            if (entry.getValue() > 0) {
                res.add(entry.getKey() + "(" + entry.getValue() + ")");
            }
        }

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

import (
	"fmt"
	"strconv"
	"strings"
)

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
	}

	graph := map[string][]string{}
	for _, pair := range synonyms {
		comma := strings.IndexByte(pair, ',')
		a := pair[1:comma]
		b := pair[comma+1 : len(pair)-1]
		graph[a] = append(graph[a], b)
		graph[b] = append(graph[b], a)
	}

	visited := map[string]bool{}
	res := make([]string, 0)
	for name := range graph {
		if visited[name] {
			continue
		}

		stack := []string{name}
		visited[name] = true
		sum := 0
		best := name

		for len(stack) > 0 {
			cur := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			sum += countMap[cur]
			if cur < best {
				best = cur
			}

			for _, next := range graph[cur] {
				if !visited[next] {
					visited[next] = true
					stack = append(stack, next)
				}
			}
		}

		if sum > 0 {
			res = append(res, fmt.Sprintf("%s(%d)", best, sum))
		}
	}

	for name, cnt := range countMap {
		if _, ok := graph[name]; ok {
			continue
		}
		if cnt > 0 {
			res = append(res, fmt.Sprintf("%s(%d)", name, cnt))
		}
	}

	return res
}

相似题目

题目	难度	考察点
721. 账户合并	中等	并查集
547. 省份数量	中等	并查集
684. 冗余连接	中等	并查集
399. 除法求值	中等	图遍历
990. 等式方程的可满足性	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/89929055