Advertisement
kai-rocket

Group Anagrams

Aug 25th, 2021
1,100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.98 KB | None
  1. class Solution:
  2.    
  3.     # Runtime: O(n * mlogm), where n is len of strs, and m is len of longest word
  4.     # Space: O(nm)
  5.     def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  6.         # Groups is a dict where key is sorted str and value is list of strings from strs that are anagrams of sorted str
  7.         groups = {}
  8.        
  9.         # For s in strs
  10.         for s in strs:
  11.             # Generate a sorted version of s. Strings that are anagrams should have the same sorted version.
  12.             sorted_s = ''.join(sorted(s))
  13.             # If s matches any group, add s to group
  14.             if sorted_s in groups:
  15.                 groups[sorted_s].append(s)
  16.             # Else, create new group with s in it
  17.             else:
  18.                 groups[sorted_s] = [s]
  19.        
  20.         # Convert groups to list and return group lists
  21.         group_lists = []
  22.         for sorted_str, str_group in groups.items():
  23.             group_lists.append(str_group)
  24.         return group_lists
Advertisement
RAW Paste Data Copied
Advertisement