/
721_Accounts_Merge.swift
80 lines (64 loc) · 2.23 KB
/
721_Accounts_Merge.swift
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
68
69
70
71
72
73
74
75
76
77
78
79
import Foundation
class Solution {
func accountsMerge(_ accounts: [[String]]) -> [[String]] {
var emailToNameMap = [String: String]()
var graph = [String: Set<String>]()
for account in accounts {
let (name, emails) = (account[0], account[1...])
for email in emails {
if graph[emails.first!] == nil {
graph[emails.first!] = Set<String>()
}
graph[emails.first!]?.insert(email)
if graph[email] == nil {
graph[email] = Set<String>()
}
graph[email]!.insert(emails.first!)
emailToNameMap[email] = name
}
}
var seen = Set<String>()
var result = [[String]]()
for (node, _) in graph {
if !seen.contains(node) {
seen.insert(node)
var nodeStack = [String]()
nodeStack.append(node)
var connectedNodes = [String]()
while !nodeStack.isEmpty {
let currentNode = nodeStack.popLast()
connectedNodes.append(currentNode!)
for neighbour in graph[currentNode!]! {
if !seen.contains(neighbour) {
seen.insert(neighbour)
nodeStack.append(neighbour)
}
}
}
result.append([emailToNameMap[node]!] + connectedNodes.sorted(by: <))
}
}
return result
}
}
/*
[
["John", "johnsmith@mail.com", "john00@mail.com"],
["John", "johnnybravo@mail.com"],
["John", "johnsmith@mail.com", "john_newyork@mail.com"],
["Mary", "mary@mail.com"]
]
map[email:name]
email=key / name-idx=value
ohnsmith@mail.com = j,0; j,2
john00@mail.com = j,0
johnnybravo@mail.com = j,1
john_newyork@mail.com = j,2
mary@mail.com = m,3
[
["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],
["John", "johnnybravo@mail.com"],
["Mary", "mary@mail.com"]]
Graph problem, consider emails as node and names as edges
it looks like disjoint set problem, where every set will be the answer after merging.
*/