49. Group Anagrams

Approach 1

Using Sorted string as key

class Solution
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = collections.defaultdict(list)
        for string in strs:
            s = ''.join(sorted(string))
            res[s].append(string)
        return res.values():        

1. Create an empty dictionary using the collections.defaultdict function. The defaultdict function returns a dictionary-like object that provides a default value for a nonexistent key, in this case, an empty list. This is useful for when we encounter a new key, we don't need to check if it exists first.
2. Loop through each string in the input list
3. For each string, we sort the characters in the string using the sorted function, which returns a sorted list of characters. We then join the sorted characters back into a string using the join method with an empty separator to create a key s.
4. We add the original string to the list associated with the key ?in the dictionary using the append method.
5. Finally, we return a list of the values in the dictionary using the values method, which returns a list of all the values in the dictionary.

Time Complexity: O(N*K*logK), where N is the number of words, and K is the length of a word.

Space Complexity: ?O(N*K)

Approach 2

Using tuple as key

class Solution
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        words = collections.defaultdict(list)
        for word in strs:
            chars = [0] * 26
            for char in word:
                chars[ord(char) - ord('a')] += 1
            words[tuple(chars)].append(word)
        return words.values():        

In Python, a tuple can be used as a key in a dictionary. This is useful in situations where you need to create a unique identifier for a set of values that can be used as a key.

When a tuple is used as a key, it becomes an immutable object that can be used as a dictionary key. Since dictionaries in Python require their keys to be hashable and immutable, using a tuple as a key is a good choice.

1. Initializes a defaultdict named words. A defaultdict is like a regular dictionary, but if you try to access a non-existent key, it creates a new entry for it with a default value. In this case, the default value is an empty list.
2. It loops through each string word in the input list.
3. For each word, create a list of integers named chars with length 26. This is because there are 26 lowercase letters in the English alphabet.
4. It loops through each character char in the string word, and increments the corresponding entry in the chars list. For example, if char is 'a', it increments the first element of chars, which corresponds to the letter 'a'.
5. Once it has processed all the characters in word, it converts chars to a tuple and uses it as a key to access the words dictionary. This key is unique to each set of anagrams because it represents the count of each letter in the word.
6. It appends word to the list of words corresponding to the chars key in words.
7. Finally, it returns a list of lists, where each sublist contains all the anagrams in the input list. It does this by calling the values method on the words dictionary, which returns a list of all the values (i.e., the lists of anagrams).

Time Complexity: O(NK)

Space Complexity: O(NK)