Solution For Group Anagrams

Problem Statement:

Given an array of strings, group anagrams together.

Example:

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

Solution:

To solve this problem, we can utilize the fact that two strings are anagrams if and only if they have the same set of characters. In other words, if we sort the characters in each string and group strings with the same sorted form together, we will obtain groups of anagrams.

Algorithm:

1. Create an empty dictionary to store groups of anagrams.
2. Iterate through each string in the input array:
   a. Sort the characters in the string.
   b. Use the sorted string as a key to store the original string in the dictionary.
3. Return the values of the dictionary as the grouped anagrams.

Code:

Here’s the Python code that implements the above algorithm:

“`python
from typing import List

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
# Create an empty dictionary to store groups of anagrams
anagrams = {}

    # Iterate through each string in the input array
    for s in strs:
        # Sort the characters in the string
        sorted_s = "".join(sorted(s))

        # Use the sorted string as a key to store the original string in the dictionary
        if sorted_s not in anagrams:
            anagrams[sorted_s] = [s]
        else:
            anagrams[sorted_s].append(s)

    # Return the values of the dictionary as the grouped anagrams
    return list(anagrams.values())

“`

Complexity Analysis:

• Time complexity: O(nklogk) where n is the number of strings and k is the maximum length of a string. The time complexity is dominated by the cost of sorting each string.
• Space complexity: O(nk) to store the dictionary and the output array.

Step by Step Implementation For Group Anagrams

import java.util.*; 

class Solution {
    public List> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map ans = new HashMap();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

//Time Complexity: O(NKlogK), where N is the length of strs, and K is the maximum length of a string in strs. 
//The outer loop has complexity O(N) as we iterate through each string. Then, we sort each string in O(KlogK) time.

def groupAnagrams(strs):
    ans = collections.defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        ans[tuple(count)].append(s)
    return ans.values()

var groupAnagrams = function(strs) {
  // create a map to store our anagram groups
  const map = new Map();
  // loop through each string in the input array
  for (const str of strs) {
    // create a key by sorting the string
    const key = str.split('').sort().join('');
    // if the key exists in the map, push the current string into the corresponding group
    if (map.has(key)) {
      map.get(key).push(str);
    // if the key does not exist in the map, create a new group with the current string
    } else {
      map.set(key, [str]);
    }
  }
  // return the values of the map as our results
  return [...map.values()];
};

vector> groupAnagrams(vector& strs) {
    // create a map of vector of strings to store the grouped anagrams
    map, vector> anagrams;
    
    // iterate over each string in the input vector
    for (string str : strs) {
        // create a vector of characters to store the current string
        vector chars(str.begin(), str.end());
        
        // sort the characters in the vector
        sort(chars.begin(), chars.end());
        
        // check if the map already contains an entry for the sorted vector of characters
        if (anagrams.find(chars) != anagrams.end()) {
            // if an entry exists, retrieve the vector of strings associated with the sorted vector of characters
            vector& group = anagrams[chars];
            
            // add the current string to the vector of strings
            group.push_back(str);
        } else {
            // if an entry does not exist, create a new vector of strings with the current string
            vector group = {str};
            
            // insert the new vector of strings into the map
            anagrams.insert({chars, group});
        }
    }
    
    // create a vector of vector of strings to store the grouped anagrams
    vector> groupedAnagrams;
    
    // iterate over each entry in the map
    for (auto entry : anagrams) {
        // retrieve the vector of strings associated with the entry
        vector group = entry.second;
        
        // add the vector of strings to the grouped anagrams vector
        groupedAnagrams.push_back(group);
    }
    
    // return the grouped anagrams vector
    return groupedAnagrams;
}

using System; 
using System.Collections.Generic; 
using System.Linq; 

public class Solution {
    public IList> GroupAnagrams(string[] strs) {
        // create a dictionary to store the anagram groups 
        Dictionary> dict = new Dictionary>(); 
        
        // go through each string in the input array 
        foreach(string s in strs) {
            // create a key by sorting the string characters alphabetically 
            // this will group anagrams together 
            string key = String.Concat(s.OrderBy(c => c)); 
            
            // check if the key already exists in the dictionary 
            if(dict.ContainsKey(key)) {
                // if it does, add the current string to the list of anagrams 
                dict[key].Add(s); 
            }
            else {
                // if not, create a new list with the current string 
                dict[key] = new List { s }; 
            }
        }
        
        // return the values of the dictionary as a list of lists 
        return dict.Values.ToList(); 
    }
}