Group Anagrams

The “Group Anagrams” problem is a common coding challenge that is often given to software engineers during technical interviews. Essentially, the problem involves grouping a list of words into sets of anagrams – that is, words that are made up of the same letters but in a different order.

For example, the words “listen” and “silent” are anagrams of each other because they use the same letters (l, i, s, e, n, t) but in a different order. So if you were given a list of words that included “listen” and “silent”, you would need to group them together into a single set.

The challenge is to come up with an efficient algorithm to solve this problem for a large input size. The most common approach is to use a hash table or a dictionary to keep track of each set of anagrams as you iterate through the list of words. This way, you can quickly check if a word is an anagram of an existing word and add it to the appropriate set.

The “Group Anagrams” problem is a great exercise in algorithm design and data structures. It tests your ability to think critically about a problem, come up with a solution, and implement it efficiently. So if you’re preparing for a technical interview, it’s definitely a problem worth practicing!

Group Anagrams Solutions

There are several approaches to solving the “Group Anagrams” problem, each with their own advantages and disadvantages in terms of time and space complexity. Let me explain a few of these approaches in detail:

Using a Hash Table or Dictionary:

One common approach is to use a hash table or dictionary to group the anagrams together. The idea is to iterate through each word in the list, sort its letters, and then use the sorted letters as a key in the hash table. The value associated with each key is a list of words that have the same sorted letters. Here is a pseudocode implementation:

def groupAnagrams(words):
    anagrams = {}
    for word in words:
        sorted_word = ''.join(sorted(word))
        if sorted_word in anagrams:
            anagrams[sorted_word].append(word)
        else:
            anagrams[sorted_word] = [word]
    return list(anagrams.values())

The time complexity of this approach is O(nmlog(m)), where n is the number of words and m is the maximum length of a word. The space complexity is O(n*m), since we need to store each word in the hash table.

Using a Count Array:

Another approach is to use a count array to group the anagrams together. The idea is to iterate through each word in the list, count the number of occurrences of each letter, and then use the count array as a key in a dictionary. The value associated with each key is a list of words that have the same count array. Here is a pseudocode implementation:

def groupAnagrams(words):
    anagrams = {}
    for word in words:
        count = [0]*26
        for letter in word:
            count[ord(letter) - ord('a')] += 1
        count_str = ''.join(map(str, count))
        if count_str in anagrams:
            anagrams[count_str].append(word)
        else:
            anagrams[count_str] = [word]
    return list(anagrams.values())

The time complexity of this approach is O(nm), where n is the number of words and m is the maximum length of a word. The space complexity is also O(nm), since we need to store each word and its count array in the dictionary.

Using Defaultdict:

Another approach is to use the defaultdict from the collections module to simplify the code. The defaultdict allows us to specify a default value for any key that does not yet exist in the dictionary. In this case, we can specify a default value of an empty list, so that we can append new words to the appropriate list without having to check if the list already exists. Here is a pseudocode implementation:

from collections import defaultdict

def groupAnagrams(words):
    anagrams = defaultdict(list)
    for word in words:
        sorted_word = ''.join(sorted(word))
        anagrams[sorted_word].append(word)
    return list(anagrams.values())

The time complexity and space complexity of this approach are the same as the hash table approach, which is O(nmlog(m)) and O(n*m) respectively.

All three approaches are valid solutions to the “Group Anagrams” problem, but the optimal approach may depend on the specific requirements of the problem, such as time and space constraints.

Each solution has its own advantages and disadvantages, so it really depends on the specific requirements of the problem you are solving.

The hash table approach and the defaultdict approach have the same time and space complexity, which is O(nmlog(m)) and O(n*m) respectively. However, the defaultdict approach may be slightly simpler and more concise, since it uses a built-in data structure from the collections module.

The count array approach has a slightly better time complexity of O(nm) compared to the other two approaches, but it has the same space complexity of O(nm). However, it may be more complex and harder to read than the other two approaches, since it involves counting the number of occurrences of each letter.

Group Anagrams in Python:

Here is the Python code using defaultdict:

from collections import defaultdict

def groupAnagrams(words):
    anagrams = defaultdict(list)
    for word in words:
        sorted_word = ''.join(sorted(word))
        anagrams[sorted_word].append(word)
    return list(anagrams.values())

In this implementation, we first import the defaultdict from the collections module. Then, we create a defaultdict object called anagrams, with a default value of an empty list. We iterate through each word in the input list, sort its letters, and use the sorted letters as a key in the anagrams dictionary. We append each word to the list of words associated with its key. Finally, we return a list of the values in the anagrams dictionary.

Group Anagrams in Java:

Here is the Java code using HashMap and ArrayList:

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> anagrams = new HashMap<>();
        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String sortedWord = new String(chars);
            if (anagrams.containsKey(sortedWord)) {
                anagrams.get(sortedWord).add(word);
            } else {
                List<String> list = new ArrayList<>();
                list.add(word);
                anagrams.put(sortedWord, list);
            }
        }
        return new ArrayList<>(anagrams.values());
    }
}

In this implementation, we first create a HashMap object called anagrams, with keys of type String and values of type List<String>. We iterate through each word in the input array, convert it to a char array, sort its letters, and use the sorted letters as a key in the anagrams map. We add each word to the list of words associated with its key. Finally, we return a list of the values in the anagrams map.

Group Anagrams in JavaScript:

Here is the JavaScript code using Map and Array:

function groupAnagrams(words) {
  const anagrams = new Map();
  for (const word of words) {
    const sortedWord = [...word].sort().join('');
    if (anagrams.has(sortedWord)) {
      anagrams.get(sortedWord).push(word);
    } else {
      anagrams.set(sortedWord, [word]);
    }
  }
  return Array.from(anagrams.values());
}

In this implementation, we first create a Map object called anagrams. We iterate through each word in the input array, split it into an array of characters, sort the characters, and join them back into a string. We use the sorted string as a key in the anagrams map. We add each word to the array of words associated with its key. Finally, we convert the values in the anagrams map to an array and return it.

Group Anagrams in Ruby:

Here is the Ruby code using Hash and Array:

def group_anagrams(words)
  anagrams = Hash.new { |hash, key| hash[key] = [] }
  words.each do |word|
    sorted_word = word.chars.sort.join
    anagrams[sorted_word] << word
  end
  anagrams.values
end

In this implementation, we first create a Hash object called anagrams, with a default value of an empty array. We iterate through each word in the input array, split it into an array of characters, sort the characters, and join them back into a string. We use the sorted string as a key in the anagrams hash. We add each word to the array of words associated with its key. Finally, we return the values in the anagrams hash.

In all of these implementations, the defaultdict or Map data structure is used to simplify the code by providing a default value for any key that does not exist. This eliminates the need to check if a key already exists in the dictionary or map, which can make the code more concise and easier to read.