05 August 2008
根据邮件和用户名合并账户 - DFS
1) 首先创建两个映射：emailToName 和 graph。 emailToName 映射存储每封电子邮件与其对应名称的映射。图形映射表示电子邮件之间的连接，其中每封电子邮件都映射到其相邻电子邮件的列表。
2) 迭代输入帐户列表中的每个帐户。对于每个帐户，提取名称并从索引 1 开始迭代电子邮件。
3) 对于每封电子邮件，将其及其相应名称添加到 emailToName 映射中。我们还将电子邮件添加到图表中，并与其相邻的电子邮件建立连接。
4) 构建地图后，我们创建一个集合来跟踪访问过的电子邮件和一个列表来存储合并的帐户。
5) 迭代 emailToName 映射中的每封电子邮件。如果之前未访问过某封电子邮件，会从该电子邮件开始执行深度优先搜索 (DFS)。
6) 在 DFS 期间，使用堆栈来跟踪要访问的电子邮件。将当前电子邮件添加到堆栈中并将其标记为已访问。还创建一个列表组件来存储所有连接的电子邮件。
7) 通过从堆栈中弹出电子邮件、将它们添加到组件列表并探索其相邻电子邮件来执行 DFS。如果相邻电子邮件尚未被访问，将其添加到堆栈中并将其标记为已访问。
8) DFS 完成后，在组件列表中拥有所有连接的电子邮件。对组件列表中的电子邮件进行排序，并将名称添加到列表的开头。
9) 最后，将合并的帐户（名称后跟排序的电子邮件）添加到 ans 列表中。
10) 对每封未访问的电子邮件重复步骤 5-9，直到处理完所有电子邮件。返回包含合并帐户的 ans 列表。
时间复杂度为O(NKlogK)，其中N是账户总数，K是账户的最大长度。存储图和访问集的空间复杂度为O(NK)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
// Create a map to store the email to name mapping
Map<String, String> emailToName = new HashMap<>();
// Create a map to store the email to neighboring emails mapping
Map<String, List<String>> graph = new HashMap<>();
// Build the maps based on the input accounts
for (List<String> account : accounts) {
String name = account.get(0);
// Start from index 1 as index 0 contains the name
for (int i = 1; i < account.size(); i++) {
String email = account.get(i);
emailToName.put(email, name);
// Add the neighboring emails to the graph
graph.putIfAbsent(email, new ArrayList<>());
if (i == 1) {
continue;
}
graph.get(email).add(account.get(1));
graph.get(account.get(1)).add(email);
}
}
// Create a set to keep track of visited emails
Set<String> seen = new HashSet<>();
// Create a list to store the merged accounts
List<List<String>> ans = new ArrayList<>();
// Perform DFS on each email to merge accounts
for (String email : emailToName.keySet()) {
if (!seen.contains(email)) {
seen.add(email);
Stack<String> stack = new Stack<>();
stack.push(email);
List<String> component = new ArrayList<>();
// Perform DFS and add all connected emails to the component
while (!stack.isEmpty()) {
String node = stack.pop();
component.add(node);
for (String nei : graph.get(node)) {
if (!seen.contains(nei)) {
seen.add(nei);
stack.push(nei);
}
}
}
// Sort the emails in the component
Collections.sort(component);
// Add the name to the beginning of the component
component.add(0, emailToName.get(email));
// Add the merged account to the answer list
ans.add(component);
}
}
return ans;
}
}