LC 1152

Python
Python
Publish Date:   2022-08-04

Solution to LeetCode 1152 Analyze User Website Visit Pattern

LeetCode 1152

Analyze User Website Visit Pattern (Medium) [link]

Several things should be careful: 1] the score of the pattern is the number of unique users so we need to use a set data structure when adding names of patterns; 2] website should be in increasing timestamp order but the given timestamp might not be sorted; Besides, the websites should also be in increasing lexicographical order. This can be achieved by bisect.insort; 3] we want the pattern with the largest score, but if there is a tie, we want to report the first pattern in the lexicographical order. This requires a sorted dictionary by the length of user names and the pattern itself.

Time complexity O(n^3).

import collections
import itertools
import bisect

class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        n=len(username)
        dic=collections.defaultdict(list)
        for i in range(n):
            bisect.insort(dic[username[i]],(timestamp[i],website[i]))
        name=collections.defaultdict(set) # name can be duplicated
        for k,v in dic.items():
            for t in itertools.combinations([b for a,b in v],3):
                name[t].add(k)
        return sorted(name.items(),key=lambda x:(-len(x[1]),x[0]))[0][0]
Python
  TOC