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:
- Create an empty dictionary to store groups of anagrams.
- 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. - 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(); } }