49. Group Anagrams

Medium

Problem:

Take an array of strings and group them by anagram.

Input: strs = ["eat","tea","tan","ate","nat","bat"] 
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

https://leetcode.com/problems/longest-palindromic-substring/

What to learn:

sorted()

• The sorted() function returns a sorted list of the specified iterable object.

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
for word in strs:
    print(sorted(word))

• The sorted() function allows you to specify a key or function separately for sorting using the key= option.

c = ['ccc', 'aaaa', 'd', 'bb']
sorted(c, key=len)

a = ['cde', 'cfc', 'abc']
sorted(a, key=lambda s: (s[0], s[-1])) # sort by the first character, and then the last one

• The sorted() function accepts a reverse parameter as an optional argument. Setting reverse = True sorts the iterable in the descending order.

# set
py_set = {'e', 'a', 'u', 'o', 'i'}
print(sorted(py_set, reverse=True))

# dictionary
py_dict = {'e': 1, 'a': 2, 'u': 3, 'o': 4, 'i': 5}
print(sorted(py_dict, reverse=True))

# frozen set
frozen_set = frozenset(('e', 'a', 'u', 'o', 'i'))
print(sorted(frozen_set, reverse=True))

Output

['u', 'o', 'i', 'e', 'a']
['u', 'o', 'i', 'e', 'a']
['u', 'o', 'i', 'e', 'a']

Resrouce: https://www.programiz.com/python-programming/methods/built-in/sorted

sort()

sort() will sort the list in-place, mutating its indexes and returning None.

alist.sort()
alist = blist.sort() # None

Solutions:

class Solution:
    def groupAnagrams(strs: List[str]) -> List[List[str]]:
        new_list = []
        final_list = []
        for s in strs:
            new_dict = collections.Counter(s)
            new_list.append(dict(new_dict))
            print(s)
    
        for l in new_list:
            tmp_list = []
            for index, item in enumerate(new_list):
                s = ""
                if item == l:
                    tmp_list.append(strs[index])
            # Remove duplicates
            if tmp_list not in final_list:
                final_list.append(tmp_list)
    
        return final_list

Another approach

The simplest way to determine anagrams is to compare them after sorting.

1. Construct a dictionary with sorted strings as keys.

2. Add anagrams that end up having the same key to the dictionary.

3. Return only the values of the dictionary.

class Solution:
    def groupAnagrams(strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list)
        
        for word in strs:
            anagrams[''.join(sorted(word))].append(word)
        return anagrams.values()