-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathleetcode-811-subdomain-visit-count.swift
195 lines (146 loc) · 6.75 KB
/
leetcode-811-subdomain-visit-count.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
/**
Copyright (c) 2020 David Seek, LLC
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE
OR OTHER DEALINGS IN THE SOFTWARE.
https://leetcode.com/problems/subdomain-visit-count/
A website domain like "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com", and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.
Now, call a "count-paired domain" to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be "9001 discuss.leetcode.com".
We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.
Example 1:
Input:
["9001 discuss.leetcode.com"]
Output:
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation:
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.
Example 2:
Input:
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output:
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation:
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.
Notes:
The length of cpdomains will not exceed 100.
The length of each domain name will not exceed 100.
Each address will have either 1 or 2 "." characters.
The input count in any count-paired domain will not exceed 10000.
The answer output can be returned in any order.
*/
/**
Big O Annotation
Time complexity O(n) where n is the amount of elements in nums.
Space complexity O(n) where n is the amount of elements in nums.
*/
func subdomainVisits(_ cpdomains: [String]) -> [String] {
let domainsMap = getMapping(for: cpdomains)
return getUnsortedVisitCount(forMappedDomains: domainsMap)
}
/**
- Parameters:
- domainsMap: A dictionary of domains and their visit counts
- returns:
An unsorted array of domains and their visit counts in the format: "[count] [domain]"
- Important:
Time complexity is O(n) where n is the number of elements in domainsMap
*/
private func getUnsortedVisitCount(forMappedDomains domainsMap: [String: Int]) -> [String] {
var output: [String] = []
for (key, value) in domainsMap {
output.append("\(value) \(key)")
}
return output
}
/**
- Parameters:
- cpdomains: An array of domain visits in the format: "[count] [domain]"
- returns:
A dictionary of key: String (domain name) and value: Integer (visit count)
- Important:
Time complexity is O(n) where n is the number of elements in cpdomains
*/
private func getMapping(for cpdomains: [String]) -> [String: Int] {
var map: [String: Int] = [:]
for cpdomain in cpdomains {
/**
First separate the visit count from the domain
example before: "1001 davidseek.com"
example after: ["1001", "davidseek.com"]
*/
let components = cpdomain.components(separatedBy: " ")
/**
Get an integer from the visit count.
We're forcing the conversion as stated in the
description that it is guaranteed to be valid.
*/
let counter = Int(components[0])!
// Next we get the current domain
let fullDomain = components[1]
// ... and split it by the dots
let subDomains = fullDomain.components(separatedBy: ".")
/**
Now we want to add first the full domain
for example "discuss.leetcode.com"
*/
var domains: [String] = [fullDomain]
/**
The problem notes did state that we have at most
3 components ("Each address will have either 1 or 2 "." characters.")
Therefore we have either 2 or 3 subDomains.
*/
if subDomains.count == 3 {
/**
If so, we now get the parent.
For example for "discuss.leetcode.com"
we now have ["leetcode", "com"]
*/
let parentDomainComponents: [String] = Array(subDomains[1...2])
// And we join them back together to get "leetcode.com"
let parentDomain = parentDomainComponents.joined(separator: ".")
// We add "leetcode.com"
domains.append(parentDomain)
// And we add just the "com"
domains.append(subDomains[2])
// leetcode.com
} else {
/**
If we have less than 3 parts, our starting domain is
for example "leetcode.com" and since we've already added
the full domain, we now just need to add the "com"
*/
domains.append(subDomains[1])
}
/**
Lastly we need to iterate through our
2-3 domains and adjust their counter.
This operation still leaves us with
a linear parent loop as the worst case,
O(n * 3) has a constant and we're dropping
the constant to get O(n)
*/
for domain in domains {
// Check if the domain exists in the map
if let mapped = map[domain] {
// ... if so update the counter
map[domain] = mapped + counter
} else {
// ... if not, add the counter
map[domain] = counter
}
}
}
return map
}