Initial Solution
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res:List[List[str]] = [] # 2d array
for i, str_ in enumerate(strs):
found = False
for subList in res:
if self.isAnagram(subList[0], str_):
# add to the group
subList.append(str_)
found = True
# not a sublist
if not found:
res.append([str_])
return res
def isAnagram(self, str1, str2):
if len(str1) != len(str2) :
return False
seen = {}
for char in str2:
seen[char] = seen.get(char, 0) + 1
for char in str1:
if char not in seen:
return False
seen[char] -= 1
if seen[char] < 0 :
return False
return True
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n * m * k) where n is the number of strings, m is the average length of each string, and k is the average number of groups. For each string, we potentially compare it against all existing groups using the isAnagram function which takes O(m) time.
Space Complexity: O(n * m) to store all strings in the result list, plus O(m) for the temporary hashmap used in isAnagram function.
What I didn’t know
•
sorted vs sort
sorted() returns a new sorted list and can be used on any iterable, while sort() is a list method that sorts the list in-place and returns None. For example, sorted("cat") returns ['a', 'c', 't'], but "cat".sort() would raise an error since strings don't have a sort() method.
•
using found variable
Other Better Solutions
Using a hashmap with sorted strings as keys is a more efficient approach. By sorting each string and using it as a key, all anagrams will naturally map to the same key. This reduces the time complexity significantly since we don't need to compare each string against existing groups.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_map = {}
for s in strs:
# Sort the string to use as a key
sorted_str = ''.join(sorted(s))
# Add to existing group or create new group
if sorted_str in anagram_map:
anagram_map[sorted_str].append(s)
else:
anagram_map[sorted_str] = [s]
return list(anagram_map.values())
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n * m * log m) where n is the number of strings and m is the average length of each string. The sorting operation takes O(m * log m) for each string, and we do this n times. The hashmap lookup and insertion operations are O(1) on average.
Space Complexity: O(n * m) to store all strings in the hashmap and the result list. The sorted string keys also take O(m) space but this is temporary for each iteration.