49_Group Anagrams
Last updated
Last updated
Level: medium
Tag: string, hash table
With sort. Create a dictionary to store sorted non-duplicated elements as keys, and corresponding items in the strs list as values. Keys should be tuple, because tuple is immutable but list is mutable. After sorting a string, the result is a list. So we need to transfer the list to tuple. Values are stored in list.
Without sort, use count table. Create a dictionary to store count table as keys, corresponding items in the strs list as values. We need to transfer the count table to tuple as well.
Time Complexity: , where n
is the length of strs
, and k
is the maximum length of a string in strs
. The outer loop has complexity as we iterate through each string. Then, we sort each string in time.
Space Complexity: , the total information content stored inans
.
Time Complexity: , where n
is the length ofstrs
, and k
is the maximum length of a string instrs
. Counting each string is linear in the size of the string, and we count every string.
Space Complexity: , the total information content stored inans
.