Solving the “Group Anagrams” Problem on LeetCode

Are you ready to dive into the world of data structures, algorithms, and problem-solving? In this blog post, we’ll explore an interesting coding challenge from LeetCode called “Group Anagrams.” The problem involves grouping anagrams from a list of words, and we’ll walk through a Python solution to tackle it efficiently.

Understanding the Problem

The “Group Anagrams” problem asks us to group words that are anagrams of each other together. An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once. For example, “listen” and “silent” are anagrams.

Given a list of words, we need to group the anagrams together and return the groups as a list of lists. Here’s a visual representation of the problem:

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

The Solution

To solve this problem, we can use a Python dictionary to group the anagrams. The key insight here is that when you sort the characters of an anagram, they will have the same sorted representation. For example, if we sort the characters of “eat,” “tea,” and “ate,” they will all become “aet.” So, we can use this sorted representation as a key in our dictionary.

Here’s the Python code to solve the problem:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        map = dict()
        for i in range(0,len(strs)):
            ch = [0] * 26
            ch_array = list(strs[i])
            for c in ch_array:
                ch[ord(c) - ord('a')] += 1
            str_key = tuple(ch)
            if str_key in map:
                map[str_key].append(strs[i])
            else:
                map[str_key] = [strs[i]]
        
        return map.values()

In this code:

I iterate through the list of words using a for loop with the variable i.

Inside the loop, I create a list ch of 26 zeros, which I will use to represent the count of each character in the word.

I convert each word into a list of characters using ch_array.

Then, I iterate through the characters ch_array and update the count of each character in the ch list. The character count is determined by the ASCII value of the character relative to 'a'.

I use a tuple of character counts str_key as the key for the dictionary. This represents the sorted representation of the characters.

I check if the str_key already exists in the map dictionary. If it exists, I append the current word to the corresponding group. If it doesn't exist, I create a new group with that str_key.

Finally, I return the values (groups of anagrams) from the map dictionary as a list of lists using map.values().

Complexity Analysis

In summary, the code has a time complexity of O(n * k) and a space complexity of O(n + k) in the worst case, where ’n’ is the number of words, and ‘k’ is the average word length.

Conclusion

The “Group Anagrams” problem on LeetCode is a fun challenge that demonstrates the importance of choosing the right data structures and algorithms for the task at hand. In this case, I’ve used a dictionary to efficiently group anagrams from a list of words. Solving problems like this not only improves your coding skills but also enhances your problem-solving abilities.

I hope this blog post has been informative and helpful as you explore the world of algorithmic problem-solving. Happy coding!