Python no sort solution, any suggestion?


  • 0

    If we sort every string and build a hash table, like many answers, the time complexity will be O(nklogk) where k is the average length of words in the list

    Actually we can use a 26 number string to represent the key to a group of string, for example "abc" and "cba" can both be represented as '111000000000...000'

    But the code is actually slow, I guess it is because the strings in test cases are short.

    Any suggestion to improve my code?

    from collections import defaultdict, Counter
    
    class Solution(object):
        def groupAnagrams(self, strs):
            """
            :type strs: List[str]
            :rtype: List[List[str]]
            """
            
            def unique_key(s):
                # n
                countDic = Counter(s)
                return ''.join([str(countDic[chr(ord('a')+i)]) for i in range(26)])
                
                # # nlogn
                # return ''.join(sorted(s))
            
            groupDic = defaultdict(list)
            for s in strs:
                groupDic[unique_key(s)].append(s)
                
            return [groupDic[key] for key in groupDic]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.