Time: , space:
.
class Solution:
def mostVisitedPattern(
self, username: List[str], timestamp: List[int], website: List[str]
) -> List[str]:
# O(N * lgN)
info = sorted([(t, u, w) for t, u, w in zip(timestamp, username, website)])
def get_patterns(sites):
patterns = []
for i in range(len(sites)):
for j in range(i + 1, len(sites)):
for k in range(j + 1, len(sites)):
patterns.append((sites[i], sites[j], sites[k]))
return patterns
# O(N)
user_visits = {}
for _, u, w in info:
if u not in user_visits:
user_visits[u] = [w]
else:
user_visits[u].append(w)
user_patterns = {}
# O(N^3)
for u in username:
visits = user_visits[u]
user_patterns[u] = set(get_patterns(visits))
def get_score(p):
nonlocal user_patterns
score = 0
for u, patterns in user_patterns.items():
if p in patterns:
score += 1
return score
max_score = 0
max_pattern = None
website = [w for _, _, w in info]
# O(N^3)
for p in get_patterns(website):
# O(N)
score = get_score(p)
if score > max_score:
max_score = score
max_pattern = p
elif score == max_score and max_pattern and p < max_pattern:
max_pattern = p
return max_pattern
Leave a comment