Group Anagrams - LeetCode Problem

Problem Description

In the "Group Anagrams" question, we are given an array of strings and we need to group the anagrams. An anagram is a word formed by rearranging the letters of another word, such as cinema, formed from iceman.

For example:

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

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

Solution

We can solve this problem by grouping the words that are anagrams together. One way to do this is by using a dictionary.

We can loop through each word in the array, sort the letters of the word, and use the sorted letters as the key in our dictionary. We can then add the original word to the list of values for that key.

Here's the code:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}
        for word in strs:
            key = tuple(sorted(word))
            anagrams[key] = anagrams.get(key, []) + [word]
        return list(anagrams.values())

Complexity Analysis

The time complexity of this solution is O(NK log K), where N is the length of the input array and K is the maximum length of a string in the array. This is because we need to sort each string, which takes O(K log K) time, and we do this for each of the N strings in the array.

The space complexity is O(NK), because in the worst-case scenario, all the strings are anagrams of each other and we need to store all of them in the dictionary.

Conclusion

In this LeetCode question, we learned how to group anagrams using Python. We used a dictionary to store the anagrams and sorted the letters of each word to group them. This was a fun way to learn Python and practice our problem-solving skills! Happy coding! 😎