DEV Community

Cover image for LeetCode Challenge: Group Anagrams
Bharath Sriraam R R
Bharath Sriraam R R

Posted on

2

LeetCode Challenge: Group Anagrams

I've always wondered if Anagrams and Palindromes will ever be useful in real life. Sometimes, I think of a use case but just checking if 2 things are anagrams or palindromes doesn't really prove to be useful.

However, problems like this mess with your brain in a way that makes them fearsome and I like stuff like that which is why I respect them despite their uselessness.

Problem

Given an array of strings, group anagrams together.

Example:

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

Note:
All inputs will be in lowercase.
The order of your output does not matter.

Approach 1: The Lazy method

hyouka lazy

If you're lazy like me then you'll know that the laziest way to code if 2 strings are anagrams is to sort them and check for equality.

Algorithm:

  1. Initialize a Hash Map called groups
  2. Iterate through the array
  3. For each string find the sorted string which is the key and append the string to the list of anagrams.
  4. Return the list of all values in the hash map.

Code:

def approach1(arr):
    groups = {}

    for s in arr:
        key = ''.join(sorted(list(s)))
        groups[key] = groups.get(key, []) + [s]

    return list(groups.values())

Complexity Analysis:

Time Complexity: O(n*k*log(k)), where n is the length of arr, and k is the maximum length of a string in strs. 

Space Complexity: O(n*k), the size of the hash map

Approach 2: Paying Attention

hyouka serious

The above approach would have worked for any kind of data where each element is quantifiable.

But in this situation our data space is limited.

We are only dealing with lowercase english alphabets. In other words, there are only 26 possible characters in each string.

So, we can use the frequency of each alphabet to uniquely group anagrams.

But, what will the key be for our new hashmap?

The array of 26 frequencies will be unique but we can't keep an array as a key in a normal hashmap(language exceptions excluded).

Until now we've used either numbers or strings as the key.
If we can transform our array into a number or a string then our problem will be solved.

What could this transformer function be?

goku transform gif

How about constructing a string with some non-numerical character between consecutive numbers?

numbers separated by random character sketch

Now, that we know the algorithm let's code!

Code:

def approach2(arr):
    groups = {}
    for s in arr:
        freq = [0 for i in range(26)]

        for c in s:
            freq[ord(c) - ord('a')] += 1

        freq = list(map(str, freq))
        key = ':'.join(freq)

        groups[key] = groups.get(key, []) + [s]

    return list(groups.values())

Complexity Analysis:

Time Complexity: O(n*k), where n is the length of arr, and k is the maximum length of a string in strs. 

Space Complexity: O(n*k), the size of the hash map

Summary

Paying attention is very important to make those "wow" optimizations.

The replit for this problem:

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay